Chapter 19 Binary Search Tree

Binary tree is a very beautiful data structure, so the code is supposed to be beautiful as well. If not, think twice!

Binary Tree is a simplified version of Graph, or a complex version of linked list!!

Three tools to solve 90% binary tree problems:

  • Recursion
  • DFS
  • BFS

It tests the understanding of DFS, BFS, Recursion.

Transform/Manipulation of Binary Tree

19.1 108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

     / \
   -3   9
   /   /
 -10  5

19.2 109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST



Another AC code to use lower median as root:

Linked List Lower Median:

Linked List Upper Median:


19.3 AVL tree

An AVL tree is a BST where the height of every node and that of its sibling differ by at most 1.

19.4 Order Statistic Tree and Stream Median Tree

19.5 Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: [2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far.

For example:

findMedian() -> 1.5
findMedian() -> 2

19.5.1 Method 1: Two heaps

T: O(LogN)

19.5.2 Method 2: Order Statistic Tree

T: O(LogN)

CLRS p473 Amortized weight-balanced trees

19.5.3 Method 3: Median Binary Tree

T: O(1)

This solution uses an ordinary binary tree for simplicity’s sake, which means it is likely to be unbalanced. Given enough time one may well use a balanced binary tree implementation to guarantee O(logn) runtime for addNum(). It is easy to see that findMedian() runs in O(1).

By using a binary tree, we can easily keep the input numbers in nondecreasing order. Observe that whenever a number is added, the numbers used to calculate the median never shift by more than 1 position (in an imagined array representation) to the left or to the right. Let’s see an example: [2], number used to calculate median is 2. [2,3], numbers used are 2,3 (expanding 1 to right) [0,2,3], use 2 (shrinking 1 to left) [0,1,2,3], use 1,2 (expanding 1 to left) [0,1,2,3,4], use 2 (shrinking 1 to right) ….and so on.

With this observation, in MedianFinder I employ 2 variables medianLeft and medianRight to keep track of numbers we need to calculate the median. When size is odd, they point to the same node, otherwise they always point to 2 nodes which have predecessor/successor relationship. When adding a node, we just need to check the size of our MedianFinder tree, then depending on whether the new number is inserted to the left, inbetween, or to the right of our 2 median trackers, we will change medianLeft and medianRight to point to the correct nodes. Because the position never shifts more than 1, we can simply use predecessor() or successor() on the desired node to update it. Those 2 methods run in O(logn) when the tree is balanced, hence the O(logn) runtime of addNum().

public class MedianFinder {
    private Node root;
    private Node medianLeft;
    private Node medianRight;
    private int size;
    public MedianFinder() { }
    // Adds a number into the data structure.
    public void addNum(int num) {
        if (root == null) {
            root = new Node(num);
            medianLeft = root;
            medianRight = root;
        } else {
            ////!!!! adjust medianLeft and medianRight
            if (size % 2 == 0) {
                if (num < {
                    medianRight = medianLeft;
                } else if ( <= num && num < {
                    medianLeft = medianLeft.successor();
                    medianRight = medianRight.predecessor();
                } else if ( <= num) {
                    medianLeft = medianRight;
            else {
                if (num < {
                    medianLeft = medianLeft.predecessor();
                else {
                    medianRight = medianRight.successor();
    // Returns the median of current data stream
    public double findMedian() {
        return ( + / 2.0;
    class Node {
        private Node parent; //
        private Node left;
        private Node right;
        private int data;
        public Node(int data) { = data; }
        public void addNode(int data) {
            if (data >= {
              if (right == null) {
                right = new Node(data);
                right.parent = this;
            else {
              if (left == null) {
                left = new Node(data);
                left.parent = this;
        public Node predecessor() {               
            if (left != null)
                return left.rightMost();
            Node predecessor = parent;
            Node child = this;
            while (predecessor != null && child != predecessor.right) {
                child = predecessor;
                predecessor = predecessor.parent;
            return predecessor;
        public Node successor() {
            if (right != null)
                return right.leftMost();
            Node successor = parent;
            Node child = this;
            while (successor != null && child != successor.left) {
                child = successor;
                successor = successor.parent;
            return successor;
        public Node leftMost(){
            if (left == null)
                return this;
            return left.leftMost();
        private Node rightMost() {
            if (right == null)
                return this;
            return right.rightMost();

19.7 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

   / \
  2   3

Binary tree [1,2,3], return false.

用inorder traversal的结果是sorted array的性质可以解题. 下面是递归解法. 这个解法感觉很优美.

A Tree is BST if following is true for every node x:
- The largest value in left subtree (of x) is smaller than value of x.
- The smallest value in right subtree (of x) is greater than value of x. 详细的讲解,里面提到的等于的情况和CLRS的定义不同.

19.8 333. Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note: A subtree must include all of its descendants.

Here’s an example:

    / \
   5  15
  / \   \
 1   8   7

The Largest BST Subtree in this case is the highlighted one. The return value is the subtree’s size, which is 3.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

19.8.2 Algo 2:


19.9 250. Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example: Given binary tree,

             / \
            1   5
           / \   \
          5   5   5

return 4.

subtree就是指,在一个tree里的某一个node,以及这个node的所有descendants.那么从题目给的例子里,我们复合条件的subtree有4个, 左边第三层里的两个“5”算其2, 右边第二层的“5 - 5”,以及第三层的“5”也都算符合条件的subtree,所以我们返回4.

19.11 669. Trim a Binary Search Tree

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

We must visit every node once…so O(N); where N is the number of nodes in our tree.

To delete the nodes:

19.12 776. Split BST

Given a Binary Search Tree (BST) with root node root, and a target value V, split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, while the other subtree has all nodes that are greater than the target value. It’s not necessarily the case that the tree contains a node with value V.

Additionally, most of the structure of the original tree should remain. Formally, for any child C with parent P in the original tree, if they are both in the same subtree after the split, then node C should still have the parent P.

You should output the root TreeNode of both subtrees after splitting, in any order.

Example 1:

Input: root = [4,2,6,1,3,5,7], V = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
Note that root, output[0], and output[1] are TreeNode objects, not arrays.

The given tree [4,2,6,1,3,5,7] is represented by the following diagram:

        /   \
      2      6
     / \    / \
    1   3  5   7

while the diagrams for the outputs are:

        /   \
      3      6      and    2
            / \           /
           5   7         1