In-order Traversal Of Binary Tree

Method: Recursion

implement as left, node, right

public class Solution {
  public List<Integer> inOrder(TreeNode root) {
    // Write your solution here.
    List<Integer> result = new ArrayList<>();
    inOrderHelper(root, result);
    return result;
  }

  private void inOrderHelper(TreeNode root, List<Integer> result) {
    if (root == null) {
      return;
    }

    inOrderHelper(root.left, result);
    result.add(root.key);
    inOrderHelper(root.right, result);
  }
}

as it is a traversal, so every nodes will be visited. the Time Complexity is O(n). Space worst case is O(n), balanced will be O(logn)

Iterative way:More Important.

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  //recursive way:
  // public List<Integer> inOrder(TreeNode root) {
  //   // Write your solution here.
  //   List<Integer> result = new ArrayList<>();
  //   inOrderHelper(root, result);
  //   return result;
  // }

  // private void inOrderHelper(TreeNode root, List<Integer> result) {
  //   if (root == null) {
  //     return;
  //   }

  //   inOrderHelper(root.left, result);
  //   result.add(root.key);
  //   inOrderHelper(root.right, result);
  // }

  //iterative way:
  public List<Integer> inOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()) {
      if (cur != null) {
        stack.offerFirst(cur);
        cur = cur.left;
      } else {
        TreeNode temp = stack.pollFirst();
        result.add(temp.key);
        cur = temp.right;
      }
    }
    return result;
  }
}