[Leetcode] Binary Search Tree

Binary Search Tree

Keys of BST must be unique

Binary Search Trees are excellent data structure for storing the entries of a map. A binary search tree is a binary tree T such that each internal node v of T stores an entry (k,x) such that:

• Keys in the left subtree of k <= k.key()
• Keys in the right subtree of k >= k.key()
• only internal nodes store entries

An inorder traversal of a binary search tree should visit the keys in nondecreasing order.

Binary Tree Operations

• [Insert]

701.Insert into a Binary Search Tree (medium)

Leetcode: https://leetcode.com/problems/insert-into-a-binary-search-tree/description/

[Solution] If val < root, go left, else go right. If reach to the end of searching, append (return) the new node.

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (val < root.val) root.left = insertIntoBST(root.left, val);
        if (val > root.val) root.right = insertIntoBST(root.right, val);

        return root;
    }
}

• [Delete]

  450. Delete Node in a BST

Leetcode: https://leetcode.com/problems/delete-node-in-a-bst/description/
Instruction: https://www.youtube.com/watch?v=gcULXE7ViZw

[Solution]

1. Binary Search for the key, if key > root, go right, else go left
2. if key == root, there are three situations:
   a. root is a leaf node -> directly return null to delete root
   b. root only has left subtree -> directly return left subtree to delete root
   c. root only has right subtree -> same above
   d. root has both left and right subtree: find the maximum value in left subtree (or minimum in right subtree), replace root with that value, and delete that node

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else {
            // root.val == key
            if (root.left == null && root.right == null) return null; // if it's a leaf node, just delete it
            if (root.left == null) return root.right; // if only one side have subtree, delete root by directly skipping root
            if (root.right == null) return root.left;
            if (root.left != null && root.right != null) {
               // find the maximum value in leftsubtree or minimum value in right subtree
                TreeNode max = root.left; // find max in left
                while (max.right != null) max = max.right;
                // update root value
                root.val = max.val;
                // delete max
                root.left = deleteNode(root.left, max.val);
            }
        }
        return root;
    }
}

Recursion

• Every recursion algorithm can be converted to iterative algorithm with queue or stack
• Construct recursion:
  • Construct base case
  • Construct helper method and pass status in the parameter

783. Minimum Distance Between BST Nodes

[Solution] In-order traverse the tree and compare the distance of root and previous value.

class Solution {
    Integer min = Integer.MAX_VALUE;
    Integer prev = null;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;
    }

    public void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) dfs(root.left);

        if (prev != null) min = Math.min(min, Math.abs(root.val - prev));
        prev = root.val;
        if (root.right != null) dfs(root.right);
    }
}

230. Kth Smallest Element in a BST

Leetcode: https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

[DFS Solution] In-order traverse the tree and select the kth visited node

class Solution {
    Integer cnt = 0;
    int res = 0;
    public int kthSmallest(TreeNode root, Integer k) {
        if (root == null) return 0;
        dfs(root,k);
        return res;
    }

    private void dfs(TreeNode root, Integer k) {
        if (root == null) return;
        dfs(root.left,k);
        cnt++;
        if (cnt == k) res = root.val;
        dfs(root.right,k);
    }
}

[Binary Search Solution] Root’s left branch all smaller than root itself, while its right branch must larger than itself. First determine where the k locates, is it in the left branch or right branch by comparing k with count of left branch nodes and right branch nodes, and then find the count+1th node to return.

public int kthSmallest(TreeNode root, int k) {
        int count = countNodes(root.left);
        if (k <= count) {
            return kthSmallest(root.left, k);
        } else if (k > count + 1) {
            return kthSmallest(root.right, k-1-count); // 1 is counted as current node
        }

        return root.val; // return the left.count + 1 th node
    }

    public int countNodes(TreeNode n) {
        if (n == null) return 0;

        return 1 + countNodes(n.left) + countNodes(n.right);
    }

700. Search in a Binary Search Tree (easy)

Leetcode: https://leetcode.com/problems/search-in-a-binary-search-tree/description/

class Solution {
    TreeNode res = null;
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return root;
        if (val < root.val) searchBST(root.left, val);
        else if (val > root.val) searchBST(root.right, val);
        else res = root;
        return res;
    }
}

95. Unique Binary Search Tree II

Leetcode: https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Solution please see Dynamic Programming part

99. Recover Binary Search Tree

Leetcode: https://leetcode.com/problems/recover-binary-search-tree/description/

[Solution] See Discussion: https://leetcode.com/problems/recover-binary-search-tree/discuss/32535/No-Fancy-Algorithm-just-Simple-and-Powerful-In-Order-Traversal

class Solution {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode prev = new TreeNode(Integer.MIN_VALUE); // Avoid the first value which doesn't have a prev value

    public void recoverTree(TreeNode root) {
        helper(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void helper(TreeNode root) {
        if (root == null) return;
        helper(root.left);
        if (first == null && root.val < prev.val) {
            first = prev;
        }
        if (first != null && root.val < prev.val ) {
            second = root;
        }

        prev = root;
        helper(root.right);
    }
}

109. Convert Sorted List to Binary Search Tree

Leetcode: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

[Solution] See Two Pointers -> fast and slow

426. Convert Binary Search Tree to Sorted Doubly Linked List

Leetcode: https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/description/

[Solution]

1. Set a prevNode to remember the previous node
2. Set a headNode to remmeber the head of the linkedlist
3. in-order traverse the tree and link nodes together

class Solution {
    Node head = null;
    Node prevNode = null;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        helper(root);
        prevNode.right = head;
        head.left = prevNode;
        return head;
    }

    private void helper(Node root) {
        Node curNode = root;
        if (root == null) return;

        helper(root.left);
        // visit root
        if (prevNode == null) {
            head = root;
        } else {
            prevNode.right = curNode;
            curNode.left = prevNode;
        }
        prevNode = root;

        helper(root.right);
    }
}