Tree

Tree

1. Traversal

(1) Preorder Traversal

    // Iterative version
    public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();

       if (root == null) {
           return res;
       }

       Stack<TreeNode> stack = new Stack<>();
       stack.push(root);

       while (!stack.isEmpty()) {
           TreeNode curNode = stack.pop();
           res.add(curNode.val);

           if (curNode.right != null) {
               stack.push(curNode.right);
           }

           if (curNode.left != null) {
               stack.push(curNode.left);
           } 
       }
       return res;
    }

(2) Inorder Traversal

    // Iterative version
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curNode = root;

        Stack<TreeNode> stack = new Stack<>();
        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            else {
                curNode = stack.pop();
                res.add(curNode.val);
                curNode = curNode.right;
            }
        }
        return res;
    }

(3) Postorder Traversal

    // Iterative version
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode curNode = null, preNode = null;

        while (!stack.isEmpty()) {
            curNode = stack.peek();
            // Case 1: Traverse down the tree, put left child into stack if it exists, otherwise put right child
            if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
                if (curNode.left != null) {
                    stack.push(curNode.left);
                }
                else if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 2: Travese up from left child
            else if (curNode.left == preNode) {
                if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 3: Traverse up from right child
            else {
                res.add(curNode.val);
                stack.pop();
            }
            preNode = curNode;
        }
        return res;
    }

2. DFS and BFS in Tree

(1) BFS

This is essentially Binary Tree Level Order Traversal

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> level = null;

        while (!queue.isEmpty()) {
            int size = queue.size();
            level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();

                level.add(curNode.val);

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            res.add(level);
        }
        return res;
    }

(2) DFS

• DFS is helpful to get the size of subtree: Largest BST Subtree

    public int getTreeSize(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSize = getTreeSize(node.left);
        int rightSize = getTreeSize(node.right);

        return 1 + leftSize + rightSize;
    }

• DFS is helpful to get the height of subtree: Balanced Binary Tree

    public int getTreeHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = getTreeHeight(node.left);
        int rightHeight = getTreeHeight(node.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }

3. Binary Search Tree

1. Check if a tree is binary search tree: Validate Binary Search Tree
2. Based on the property of Binary Search Tree, we can implement Binary Search to retrieve a value: Kth Smallest Element in a BST

4.Threaded Tree (Morris Tree)

Threaded Tree can guarantee O(n) time in traversal and O(1) space

(1) Preorder Traversal

public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();

       TreeNode curNode = root;
       TreeNode preNode = null;

       while (curNode != null) {
           if (curNode.left == null) {
               res.add(curNode.val);
               curNode = curNode.right;
           }
           else {
               preNode = curNode.left;
               // Get the predecessor of curNode
               while (preNode.right != null && preNode.right != curNode) {
                   preNode = preNode.right;
               }

               // Case 1: Find the predecessor of curNode, traversing down
               if (preNode.right == null) {
                   res.add(curNode.val);
                   preNode.right = curNode;
                   curNode = curNode.left;
               }
               // Case 2: Disconnect with predecessor, traversing up
               else {
                   preNode.right = null;
                   curNode = curNode.right;
               }
           }
       }
       return res;
    }

(2) Inorder Traversal

TreeNode preNode = null;
        TreeNode curNode = root;

        while (curNode != null) {
            if (curNode.left == null) {
                res.add(curNode.val);
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null && preNode.right != curNode) {
                    preNode = preNode.right;
                }

                if (preNode.right == null) {
                    preNode.right = curNode;
                    curNode = curNode.left;
                }
                else {
                    preNode.right = null;
                    res.add(curNode.val);
                    curNode = curNode.right;
                }
            }
        }
        return res;

(3) Postorder Traversal

List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        TreeNode dummy = new TreeNode(0);
        TreeNode preNode = null, curNode = dummy;
        dummy.left = root;

        while (curNode != null) {
            if (curNode.left == null) {
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null && preNode.right != curNode) {
                    preNode = preNode.right;
                }

                // Traversing down
                if (preNode.right == null) {
                    preNode.right = curNode;
                    curNode = curNode.left;
                }
                // Traversing up, reverse the path
                else {
                    TreeNode node = preNode;
                    reverse(curNode.left, preNode);
                    while (node != curNode.left) {
                        res.add(node.val);
                        node = node.right;
                    }
                    res.add(node.val); // node is now equal to curNode.left
                    reverse(preNode, curNode.left);
                    preNode.right = null;
                    curNode = curNode.right;
                }
            }
        }
        return res;
    }

    public void reverse(TreeNode from, TreeNode to) {
        if (from == to) {
            return;
        }

        TreeNode preNode = from, curNode = from.right, nextNode = null;

        while (preNode != to) {
            nextNode = curNode.right;
            curNode.right = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
    }

5. Question Category

1. Preorder Traversal: Serialize and Deserialize Binary Tree,
2. Inorder Traversal: Recover Binary Search Tree,
3. Postorder Traversal: Binary Tree Postorder Traversal