Increasing Order Search Tree — Leetcode 897

  • Post last modified:November 9, 2022
  • Reading time:3 mins read

Introduction

  • In this article, we will solve leetcode 897 which mainly deals with the Binary search trees.
  • If you want to learn how we can manipulate pointers/references in binary search trees, then this problem is good.
  • We will look at both recursive and stack-based solutions.

Problem Statement

  • We have been given the root of the binary search tree and we need to rearrange it in a certain way.
  • As per rearrangement, we have made the leftmost node the root of the tree and every node doesn’t have a left child and has only one right child.

Example

  • In the below example, we can see leftmost node 1 becomes the root of the rearranged tree.
  • left child of each node is null and they only have right child.

Solution

Intuition

  • The basic intuion of this problem is to know that we have to modify the pointer/reference of the tree nodes.
  • Since for each root node we look up to the left node, then it makes sense to reach up to the leftmost node.
  • if the node that we are at leftmost then we initialize it as prev, since it will be useful in recursive calls.
  • We also initialize head node since we have to return the reference of head node as result. If the node that we are at leftmost node then it makes sense to initialize .
  • If the current node is not the leftmost node then we can perform our pointer manipulation.
  • We will now have the prev node and we will make prev.right pointing to the current root node.
  •  make that node as root node and prev root becomes right child of this new root .
  • If prev root has the right child then we again make a recursive call on that node and then traverse left most node as we did in case of root node .

Code

  • Here is the complete code for the recursive solution. 
   private TreeNode sol2(TreeNode root){
        if(root == null) return null;
        sol2(root.left);
        if(prev!=null){
            root.left = null;
            prev.right = root;
            
        }
        prev = root;
        if(head==null) head = root;
        sol2(root.right);
        return head;
    }
  • We can also implement a solution using a stack data structure where we keep the nodes that we traversed in the stack until we reach the leftmost node.
  • Basic pointer manipulation logic is the same.
private TreeNode sol1(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while(curr!=null || !stack.isEmpty()){
            while(curr!=null){
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if(prev!=null){
                curr.left=null;
                prev.right = curr;
            }
            if(head==null) head = curr;
            prev = curr;
            curr = curr.right;
        }
        
        return head;
        
    }

Result

  • Our code is accepted by leetcode.

Complexity

  • Time Complexity: O(N) since we are visiting each node only once
  • Space Complexity: O(H) where H is the height of the tree.

Conclusion

  • In this article we solved leetcode 897 which is one of the best problems to solve on binary search tree
  • This problem help us clarifying lots of theory knowledge with pointer manipulation understanding.

Leave a Reply