O(n) Iterative Java Solution


  • 0
    J

    In inorder traversal :
    STEP 1: starting from the current node (root) we traverse the tree all the way to the left. We go on putting these nodes in stacks as they are traversed. Pop the left node and print it or put in the result list.
    STEP 2: check to see if the last printed node has a non-null right child
    STEP 3: if the right child is found to be null in STEP 2, then go to STEP 1. Now the right child becomes the current node.
    STEP 4: If the right child in STEP 2 is null then our next node to be printed or be put in the result list would be the parent node of the last printed node. This node is on the top of the stack right now. So pop it and print. Go to STEP 2.
    Repeat these steps until the stack is empty.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            if (root == null) return new ArrayList<Integer>();
            
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode current = root;
            
            while(current != null || !stack.isEmpty()) {
                // go to the leftmost node
                while (current != null) {
                    stack.push(current);
                    current = current.left;
                }
                
                // pop the current node and display (put into the list)
                current = stack.pop();
                list.add(current.val);
                
                // set the current node to either right node if not null 
                // or else set current to null and loop again
               current = current.right;         
            }
            
            return list;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.