Tree Traversal

Populate next right ptr.

Solution 1 ： BFS + prev ptr.

Solution 2 : DFS + Map (List).

merge k sorted list.

      void dfs(List<TreeNode> res, TreeNode root, int level) {
          if (root == null) {
              return;
          }
          if (res.size() == level) {
              res.add(root);
          } else {
              res.get(level).next = root;
              result.set(level,root);
          }
          dfs(res,root.left,level + 1);
          dfs(res,root.right,level + 1);
      }

Solution 3: "two level by two level" (tricky solution)

Optimization:

Solution 1 used BFS which maintain a queue for next level node.

Could this be optimized ?

Yes. actually when we populate cur level, we can also link next level to right, and maintain head of next level. Since all nodes at next level are already linked, we will not miss any node.

    public TreeNode connect (TreeNode root) {
        TreeNode ret = root;
        //mark next level head
        TreeNode anchor = new TreeNode(-1);
        TreeNode prev = anchor;
        while (root != null) {
            if (root.left != null) {
                prev.next = root.left;
                prev = prev.next;
            } 
            if (root.right != null) {
                prev.next = root.right;
                prev = prev.next;
            }
            root = root.next;
            if (root == null) {
                 root = anchor.next;
                 //don't forget this line!s
                 anchor.next = null;
                 prev = anchor;
            }
        }
        return root;
    }

Tree Traversal

Recursion

Iterative

• with stack ?
• with parent ptr ?
• w/o stack or parent ptr ?

Inorder Traversal

Solution 1 :

Use stack.

    //stack and cur maintains all touched nodes but have't delt with.
    public void inorder (TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()) {
            if (root != null) {
              stack.push(root);
              root = root.left;
            } else {
                System.out.println(stack.peekFirst().val);
                root = stack.pop().right;
            }
        }
    }

Solution 2 calling firstNode and nextNode

TreeNode firstNode(TreeNode root) {
    if (root == null) {
        return root;
    }
    while (root != null) {
        root = root.left;
    }
    return root;
}

//next node

case 1 : if cur node has right subtree, next node is firstNode in right subtree.

case 2 : if cur node doesn't have right subtree, next node is parent node which cur node is a right child. (last seen parent root which is in its right subtree).

TreeNode nextNode(TreeNode root, TreeNode cur) {
    //case 1
    if (cur.right != null) {
        return firstNode(cur.right);
    }
    //case2 : ask for parent ptr first
    //if doesn't have a parent ptr.
    parent = null;
    while(root != null) {
        if(root == cur) {
            return parent;
        } else {
            parent = root;
            root = root.right;
        }
    }
    return parent;
}