Solution by vinnyoodles


  • 0
    V

    Approach #1 Recursive [Accepted (Trivial)]

    Intuition

    Implement in order traversal using recursion.

    Algorithm

    An in order traversal simply visits the left sub tree, the current node and then the right sub tree. When visiting a sub tree, the traversal has to hit all of the nodes in the sub tree before performing any logic on the current node.

    This is trivial to implement in recursion because we can just call the helper function on an entire sub tree before performing the logic with the current node. All that is needed to complete this are a few base cases to check for null pointers.

    Java

    public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> list = new ArrayList<>();
      // Initial base case.
      if (root == null) return list;
    	
      traverseRecursively(root, list);
      return list;
    }
    
    public void traverseRecursively(TreeNode node, List<Integr> list) {
      // We should not add any null nodes.
      if (node.left != null) {
        traverseRecursively(node.left, list);
      }
    	
      // The logic to be performed on the current node 
      // is simply adding to an array list.
      list.add(node.val);
    	
      if (node.right != null) {
    	traverseRecursively(node.right, list);
      }
    }
    

    Complexity Analysis

    • Time complexity: $$O(n)$$. n is the number of nodes in the tree and each node is visited once.

    • Space complexity: $$O(k)$$. The recursive call stack grows to at most k where k is the max height or length of the tree.

    Approach #2 Iterative [Accepted]

    Intuition

    Implement in order traversal using a stack (to mimic the recursive call stack) and while loops.

    Algorithm

    The algorithm is the same: visit the left sub tree, perform logic on the current node then visit the right sub tree. The tricky part is when visiting the left sub tree, the algorithm must halt the current iteration and continue down the left sub tree until it hits the last left node. This is because an in order traversal always begins with the left most node. In terms of a binary search tree, the left most node is the smallest node.

    To achieve this haltng mechanism, we must add an additional while loop that adds all possible left nodes and call continue such that the current iteration will stop so that we can add the lesser nodes before the current.

    Because we are halting the current iteration before we can add the node's value to the array list, it must be added back onto the stack in the correct location (before all the left nodes).

    Java

    public List<Integer> inorderTraversal(TreeNode root) {
      // Mimics the recursive call stack.
      Stack<TreeNode> stack = new Stack<>();
    
      // A set in order to determine a left node has already been visited or not.
      HashSet<TreeNode> set = new HashSet<>();
      List<Integer> list = new ArrayList<>();
      stack.push(root);
      set.add(root);
      if (root == null) return list;
    
      while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
    
        TreeNode left = node.left;
        TreeNode right = node.right;
        boolean hasLeft = false;
        if (left != null && !set.contains(left)) {
          // Push the current node back into the stack because if left exists then 
          // it will not be added in this current iteration
          stack.push(node);
          hasLeft = true;
        }
    
        // This inner while loop is needed to add all the 
        // left nodes in the current tree.
        // When going back up the tree, it would potentially
        // re-add duplicate left nodes, so use the hashset 
        // to prevent this.
        while (left != null) {
          if (!set.contains(left)) {
            stack.push(left);
            set.add(left);
          }                    
          left = left.left;
        }
    
        // This is the halting mechanism that prevents adding the
        // current node before the left nodes have been added.
        if (hasLeft) {
          // We have to stop the current iteration to add all the left nodes first. 
          continue;
        }
    
        list.add(node.val);
    
        // The right subtree is not as complex.
        if (node.right != null) {
          stack.push(node.right);
        }
      }
    
      return list;
    }
    

    Complexity Analysis

    • Time complexity: $$O(n)$$. n is the number of nodes in the tree and each node at least once and root nodes with a left child are visited at most twice (due to re-adding back to the stack).

    • Space complexity: $$O(n)$$. The hashset will contain all nodes once they are visited.


Log in to reply
 

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