Binary Tree Inorder Traversal

Question:

Given a binary tree, return the inorder traversal of its nodes' values.

Solution : Iterative

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorder=new ArrayList<Integer>();
        if(root==null) return inorder;
        TreeNode pointer=root;
        LinkedList<TreeNode> stack=new LinkedList<>();
        while(pointer!=null || !stack.isEmpty()){
            while(pointer!=null){
                stack.push(pointer);
                pointer=pointer.left;
            }
            pointer=stack.pop();
            inorder.add(pointer.val);
            pointer=pointer.right;
        }
        return inorder;
    }
}

def inorder_tra(root):
    res = []
    ptr = root
    tra_stack = []
    while ptr or tra_stack:
        while ptr:
            tra_stack.append(ptr)
            ptr = ptr.left
        cur = tra_stack.pop()
        res.append(cur.value)
        ptr = cur.right
    return res

Solution : Morris Inorder Traversal

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorder=new ArrayList<Integer>();
        if(root==null) return inorder;
        TreeNode pre=null;
        while(root!=null){
            if(root.left==null){
                inorder.add(root.val);
                root=root.right;
            }else{
                pre=root.left;
                while(pre.right!=null && pre.right!=root) {
                    pre=pre.right;
                }
                if(pre.right==null){
                    pre.right=root; root=root.left;
                } else {
                    pre.right=null;
                    inorder.add(root.val);
                    root=root.right;
                }
            }
        }
        return inorder;
    }
}

Applications

Check if a Binary Tree is a Binary Search Tree

boolean isBST(TreeNode root){
    if(root==null) return true;
    int pre=Integer.MIN_VALUE;
    LinkedList<TreeNode> stack=new LinkedList<>();
    TreeNode ptr=root;
    while(ptr!=null || !stack.isEmpty()){
        while(ptr!=null){
            stack.push(ptr);
            ptr=ptr.left;
        }
        ptr=stack.pop();
        if(ptr.val<pre) return false;
        pre=ptr.val;
        ptr=ptr.right;
    }
    return true;
}

given one BST, find the Kth minimum value or Kth maximum value

public int kthSmallest(TreeNode root, int k) {
        LinkedList<TreeNode> stack=new LinkedList<>();
        TreeNode ptr=root;
        while(ptr!=null || !stack.isEmpty()){
            while(ptr!=null){
                stack.push(ptr);
                ptr=ptr.left;
            }
            ptr=stack.pop();
            if(k==1) return ptr.val;
            ptr=ptr.right;
            k--;
        }
        return 0;//not reachable
    }

For Kth maximum

public int kthSmallest(TreeNode root, int k) {
        LinkedList<TreeNode> stack=new LinkedList<>();
        TreeNode ptr=root;
        while(ptr!=null || !stack.isEmpty()){
            while(ptr!=null){
                stack.push(ptr);
                ptr=ptr.right;
            }
            ptr=stack.pop();
            if(k==1) return ptr.val;
            ptr=ptr.left;
            k--;
        }
        return 0;//not reachable
    }

BST Inorder Iterator

public class inorderIterator implements Iterator<TreeNode>{
    LinkedList<TreeNode> stack;
    TreeNode ptr;
    inorderIterator(TreeNode root){
        stack=new LinkedList<TreeNode>();
        if(root!=null){
            ptr=root;
            while(ptr!=null){
                stack.push(ptr);
                ptr=ptr.left;
            }
        }
    }


    public boolean hasNext(){
        return !stack.isEmpty();
    }


    public TreeNode next(){
        TreeNode tmp=stack.pop();
        TreeNode ptr=tmp.right;
        while(ptr!=null){
            stack.push(ptr);
            ptr=ptr.left;
        }
        return tmp;
    }
}

BST (with parent pointer) Inorder Iterator without Extra Space

Here, if we have parent pointer in each TreeNode, we can easily implement the inorder traversal without extra space

public inorderIterator implements Interator<TreeNode>{
    TreeNode ptr;
    inorderIterator(TreeNode root){
      ptr=root;
      if(ptr!=null){
        while(ptr.left!=null) ptr=ptr.left;
      }
    }

    public boolean hasNext(){
      return ptr!=null;
    }

    public TreeNode next(){
      TreeNode res=ptr;
      if(ptr.right!=null){
        ptr=ptr.right;
        while(ptr.left!=null) ptr=ptr.left;
      }else{
        TreeNode root=ptr.parent;
        while(root!=null){
          if(root.left==ptr) {
            ptr=root;
            break;
          }
          else {
            ptr=root;
            root=ptr.parent;
          }
        }
        if(root==null) ptr=null;
      }
      return res;
    }