Java Solution for Leetcode 897
Introduction
- In this article, we will solve leetcode 897 using Java. We will use recursion & stack to solve this problem.
Problem Statement
- Given the
rootof a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
Example
- In the below example as we can see all the nodes on the right-hand side have left child as null and left child becomes the root of the tree.
- This is kind of converting tree data structure to linear strcuture which is in increasing order.
Solution
Intuition
- This kind of problem always requires knowledge of pointer manipulation and we need to be good at handling pointers in the binary tree traversal.
- If we traverse the left node for each root until we reach the left then we can make that node the root node and make the previous root node as the right child of this new root node and the left node will be marked as null.
- Once we traverse to leftmost node i.e node 1 then we mark it as prev node and come back to previous call i.e call for node 2
- Now in case of node 2 , its root for the given call , so break the left child relationship with prev node. We make prev.right = root and root.left = null.
- We perform the same operation recursively on other nodes in our recursion call stack.
Code
Solution #1: Recursive Approach
- We have explained this approach in intuition. This is a recursive solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
TreeNode head=null;
TreeNode prev=null;
public TreeNode increasingBST(TreeNode root) {
return sol2(root);
}
private TreeNode sol2(TreeNode root){
if(root == null) return null;
sol2(root.left); // we go to the leftmost child of the root
if(prev!=null){ // if this is not the leftmost then we can do pointer
// manupulation,
root.left = null; // mark left node of root to null
prev.right = root; // prev.right points to root. see diagram mentioned in the intuition
}
prev = root;
if(head==null) head = root; // when we are at leftmost node head will be null and we can set that to root so that we can keep track of head of the result node
sol2(root.right); // once leftnode is done we move to right child and perdorm same recursion logic, i.e go to leftmost node and do the pointer manupulation
return head;
}
}
Solution#: Iterative approach
- We can also solve this problem with an iterative approach. Intuition is similar, the only difference is that we are using stack instead of the inherent call stack in recursion.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
TreeNode head=null;
TreeNode prev=null;
public TreeNode increasingBST(TreeNode root) {
return sol1(root);
}
private TreeNode sol1(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while(curr!=null || !stack.isEmpty()){
while(curr!=null){
stack.push(curr); // keep the track of visited node. we will use the stack to operate over these nodes
curr = curr.left; // move to leftmost child
}
curr = stack.pop(); // once at leftmost node , pop it
if(prev!=null){ // if we are not at the leftmost node
curr.left=null; // do the pointer manupulation
prev.right = curr;
}
if(head==null) head = curr; // if we are at the leftmost node , keep the reference to the head so that we can return the result
prev = curr;
curr = curr.right; // move to the right child once finish with root and left child
}
return head;
}
}
Result
- Our solution is accepted by leetcode.
Complexity
Space Complexity: O(N) since we are storing N nodes in the call stack
Time Complexity: O(N) since we are traversing N nodes
Conclusion
- In this article, we solved Leetcode 897 problem where we converted the binary search tree to an increasing order search tree.
- We solved using recursion and iteration both the approach
Best Seller Course
If you want to upskill your coding interview game, you can definitely check out this bestseller course