# Solving Tree-related Problems

• Binary Tree: a tree in which each node has up to two children
• Binary Search Tree: a binary tree in which every node fits a specific ordering property: all left descendants ≤ n < all right descendants.

# Complete Traversal

• Given a binary tree, determine if it is height-balanced.
• Given a binary tree, find its maximum depth.
• Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
• Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
• Invert a binary tree.
• Flatten Binary Tree to Linked List
• Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

# Partial Traversal

`public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    if (root == null) {        return null;    }    int min = Math.min(p.val, q.val);    int max = Math.max(p.val, q.val);        if (root.val >= min && root.val <= max) {        return root;    }        return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);}`
`private int getHeight(TreeNode root) {    if (root == null) {        return 0;    }    return getHeight(root.left) + 1;}`
`public int countNodes(TreeNode root) {    if (root == null) {        return 0;    }        int lh = getHeight(root.left);    int rh = getHeight(root.right);        // this means we can take the whole left subtree and the root    // we recursively need to countNodes(root.right);    if (lh == rh) {        return (1 << lh) + countNodes(root.right);    }        // otherwise, it means we can take right subtree and the root    // we resursively need to countNodes(root.left);    return (1 << rh) + countNodes(root.left);}`

--

--

## More from Zengrui Wang

Senior Software Engineer @Hulu

Love podcasts or audiobooks? Learn on the go with our new app.