22.12.23 - [CtCI] Ch.4 Trees and Graphs

[suhyunsim]

Questions

• 4.1 Route between Nodes
• 4.2 Minimal Tree
• 4.3 List of Depths
• 4.4 Check Balanced
• 4.5 Validate BST
• 4.6 Successor
• 4.7 Build Order
• 4.8 First Common Ancestor
• 4.9 BST Sequence
• 4.10 Check Subtree
• 4.11 Random Node
• 4.12 Paths with Sum

[suhyunsim]

4.5 Validate BST

Hints

• If you traversed the tree using an in-order traversal and the elements were truly in the right order, does this indicate that the tree is actually in order? What happens for duplicate elements? If duplicate elements are allowed, they must be on a specific side (usually the left).
• To be a binary search tree, it's not sufficient that theleft.value <= current.value < right.value for each node. Every node on the left must be less than the current node, which must be less than all the nodes on the right.
• If every node on the left must be less than or equal to the current node, then this is really the same thing as saying that the biggest node on the left must be less than or equal to the current node.
• Rather than validating the current node's value against leftTree.max and rightTree.min, can we flip around the logic? Validate the left tree's nodes to ensure that they are smaller than current.value.
• Think about the checkBST() function as a recursive function that ensures each node is within an allowable (min, max) range. At first, this range is infinite. When we traverse to the left, the min is negative infinity and the max is root.value. Can you implement this recursive function and properly adjust these ranges as you traverse the tree?

Things to Consider

• (1) in-order-traversal(중위: 왼-가-오)
  • ⚠️ only w/o duplicated things
• (2) definition of BST: left <= current < right
  • all left nodes must be less than or equal to the current node, which must be less than all the right nodes
  • passing down the min and max values
  • as iterate through tree -> verify against progressively narrower ranges
  1. left: (null, root) / right (root, null)
  2. left -> update max, right -> update min
  • O(N), N: number of nodes

Solution

(1) Solution: in-order-traversal

package main.java.com.poogle.cracking.Ch4TreesGraphs.Q5;

public class SolutionA {
    static Integer lastPrinted = null;
    private static boolean checkBST(TreeNode node) {
        return checkBST(node, true);
    }

    public static boolean checkBST(TreeNode node, boolean isLeft) {
        if (node == null) {
            return true;
        }

        if (!checkBST(node.left, true)) {
            return false;
        }

        if (lastPrinted != null) {
            if (isLeft) {
                if (node.data < lastPrinted) {
                    return false;
                }
            } else {
                if (node.data <= lastPrinted) {
                    return false;
                }
            }
        }
        lastPrinted = node.data;

        if (!checkBST(node.right, false)) {
            return false;
        }
        return true;
    }
}

(2) Solution: Using definition

package main.java.com.poogle.cracking.Ch4TreesGraphs.Q5;

public class SolutionB {
    private static boolean checkBST(TreeNode node) {
        return checkBST(node, null, null);
    }

    public static boolean checkBST(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }

        if ((min != null && node.data <= min) || (max != null && node.data > max)) {
            return false;
        }

        if (!checkBST(node.left, min, node.data) || !checkBST(node.right, node.data, max)) {
            return false;
        }
        return true;
    }
}

ETC