DSA 0x102 - Tree Data structure
Tree is one of most important data structure.
We all know that in Linux, the file system is starting from the directory.The root directory contains many sub directories such as etc, var, home... We can go into these sub directories and some times they have another set of directories inside. This is why walking through directories is literally called traversing the tree.
In web development, we have something called DOM which is an acronym for Document Object Model.<html> is the root, <head> and <body> are its children. When we write document.querySelector, we are running a tree search.
In Databases whenever we create an index, it is a tree. A query returning in milliseconds from a table of fifty million rows is a tree walk of maybe four or five levels.
some times ago I was working on a Ballerina project. My goal was to daynamiclly build a Ballerina client for a given Solidity smart contract. In this a fundamental thing I had to study was the Ballerina AST. This is called the Abstract Syntax Tree. Every language has a tree with language tokens. Compilers parse source into an Abstract Syntax Tree before doing anything else. Every optimization pass is a tree transformation.
Apart from these examples, Routing tables, autocomplete, JSON parsers, etc are using Tree data structure.
The below is an example for a real world tree.
graph TD
CEO[CEO] --- CTO[CTO]
CEO --- CFO[CFO]
CTO --- D1[Engineer A]
CTO --- D2[Engineer B]
CFO --- A1[Accountant]
The CEO sits at the top. The CTO and CFO report to the CEO. Two engineers report to the CTO. Notice what is not there: no engineer reports to two managers, and no chain of reporting loops back around to the CEO.
That gives us the formal definition. A tree is a collection of nodes such that:
- There is exactly one special node called the root.
- Every other node has exactly one parent.
- There are no cycles. Following parent links from any node always terminates at the root.
Tree Terminology
To deal with the Tree data structure, we need to know some terminologies about the tree. Lets consider the below example.
graph TD
A((A)) --- B((B))
A --- C((C))
B --- D((D))
B --- E((E))
The starting point of the tree is the top most node.It is called the root node. I'm listing the most important terms here.
-
Node: a single element of the tree. Above: A, B, C, D, E.
-
Root: the one node with no parent. Here, A. Every tree has exactly one.
-
Edge: a link between a parent and a child.
-
Parent: B is the parent of D and E.
-
Child: D and E are children of B.
-
Siblings: nodes sharing a parent. D and E are siblings.
-
Leaf / External node: a node with no children. Here C, D, and E.
-
Internal node: a node with at least one child. Here A and B.
-
Ancestor: any node on the path from a node up to the root. The ancestors of D are B and A.
-
Descendant: the reverse. The descendants of B are D and E.
- Subtree: a node together with all of its descendants. B, D, E form a subtree. B is the root of that subtree.
-
Degree: the number of children a node has. B has degree 2, D has degree 0.
-
Depth of a node: the number of edges from the root down to that node. Depth of A is 0, depth of B is 1, depth of D is 2. Depth is measured downward, and it is a property of a node.
-
Height of a node: the number of edges on the longest path from that node down to a leaf. Height of D is 0 (it is a leaf), height of B is 1, height of A is 2. Height is measured upward, and the height of the tree is the height of its root.
| Node | Depth | Height |
|---|---|---|
| A | 0 | 2 |
| B | 1 | 1 |
| C | 1 | 0 |
| D | 2 | 0 |
| E | 2 | 0 |
Binary Trees
A binary tree is the most important concept we learn in this article. A binary tree has at most two children, distinguished as the left child and the right child. See this example.
graph TD
A((A)) --- B((B))
A --- C((C))
B --- D((D))
B --- E((E))
A has two children. B has two children. C has none, so it is a leaf. D and E are also leaves.
Two details that matter more than they look:
"At most two" means zero, one, or two are all legal. A node with a single child is a perfectly valid binary tree node.
Left and right are not interchangeable. These two trees contain the same two nodes, and they are still different binary trees:
graph TD
A1((A)) --- B1((B))
A1 -.- X1((N))
The below tree is not same as the above one. Above tree only has the left node while below one only has the right node.
graph TD
A2((A)) -.- X2((N))
A2 --- B2((B))
In a general tree, "the children of A" is just a set and those two would be the same thing. In a binary tree, position carries meaning. That is exactly why binary trees are important.
Why cap it at two? Because it makes every decision binary. At each node you ask one yes/no question and move one level down. That is the simplest possible branching structure that still branches.
Note that, in these examples I will be using a node with dotted line and value N to indicate a Null node. Actually there is no node. But to keep the tree shape I'm using it.
Shapes of Binary Trees
The shape of a binary tree determines its performance, so the shapes have names. You will see these in interviews and in library documentation.
Full binary tree
Every node has either 0 or 2 children. No node has exactly one.
graph TD
A((1)) --- B((2))
A --- C((3))
B --- D((4))
B --- E((5))
In a full binary tree, the number of leaves is always exactly one more than the number of internal nodes. In the above example there are 3 leaves and 2 internal nodes.
Complete binary tree
Every level is completely filled except possibly the last, and the last level fills left to right with no gaps.
graph TD
A((1)) --- B((2))
A --- C((3))
B --- D((4))
B --- E((5))
C --- F((6))
C -.- N1((N))
Level 2 has 4, 5, 6 with the rightmost slot empty. That is fine, because it filled from the left. This shape is the reason heaps can live inside a plain array with zero pointer overhead. We will lean on that hard in the heaps post.
Perfect binary tree
Every internal node has two children, and all leaves are at the same depth. Every level is completely full.
graph TD
A((1)) --- B((2))
A --- C((3))
B --- D((4))
B --- E((5))
C --- F((6))
C --- G((7))
A perfect tree of height h has exactly 2^(h+1) - 1 nodes. Here h = 2, so 2^3 - 1 = 7. This is the theoretical best case and the shape everything else is measured against.
Degenerate (skewed) tree
Every internal node has exactly one child. The tree is just a linked list.
graph TD
A((1)) ---B((2))
A -.- N1((N))
B ---C((3))
B -.- N2((N))
C ---D((4))
C -.- N3((N))
D ---E((5))
D -.- N4((N))
Height is n - 1. Every operation is O(n). This is the worst case, and later in this post you will see exactly how easy it is to create one by accident.
Balanced binary tree
For every node, the heights of the left and right subtrees differ by at most some small constant (usually 1). A balanced tree of n nodes has height O(log n), which is the whole point.
Balance is not free. Nothing in the definition of a BST enforces it. That gap is what AVL and red-black trees exist to close.
Representing a Binary Tree
We will be using Java for implementation. We can represent a binary tree in two ways in the memory.
Linked representation
Each node is an object holding a value and references to its children. This is the general-purpose choice and what we use for BSTs.
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}A missing child is null. That is it. The entire structure is nodes pointing at nodes, exactly like a linked list except each node has two forward pointers instead of one.
Array representation
For a complete binary tree, you can drop the pointers entirely and store nodes in an array by level, left to right.
Index: 0 1 2 3 4 5 6
Value: 8 3 10 1 6 14 NThe parent-child relationships become arithmetic. For a node at index i:
- left child:
2i + 1 - right child:
2i + 2 - parent:
(i - 1) / 2using integer division
graph TD
I0(("0, 8")) --- I1(("1, 3"))
I0 --- I2(("2, 10"))
I1 --- I3(("3, 1"))
I1 --- I4(("4, 6"))
I2 --- I5(("5, 14"))
I2 -.- I6(("6, N"))
Check it: node 3 sits at index 1, so its children are at indices 3 and 4, which hold 1 and 6. Correct.
This is beautiful when the tree is complete, and it is what makes binary heaps so fast. No pointers, no allocation per node, and traversing a level is a straight walk through contiguous memory.
It is terrible when the tree is sparse. A degenerate tree of 20 nodes would need an array of 2^20 - 1 slots, over a million entries, to hold 20 values. Since a BST's shape depends on insertion order and cannot be guaranteed complete, BSTs use the linked representation.
The Binary Search Tree Property
Everything so far applies to any binary tree. Now we add the one rule that turns a binary tree into a searchable one.
A Binary Search Tree (BST) is a binary tree that maintains this invariant:
For every node
x: every key inx's left subtree is less thanx, and every key inx's right subtree is greater thanx.
Here is the tree we will use for the rest of the post. Get familiar with it, because every diagram from here on is either this tree or something derived from it:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
Lets check it node by node.
- 8: left subtree is {3, 1, 6, 4, 7}, all less than 8. Right subtree is {10, 14, 13}, all greater. Good.
- 3: left is {1}, right is {6, 4, 7}. Good.
- 6: left is {4}, right is {7}. Good.
- 10: no left child, right subtree is {14, 13}, both greater. Good.
- 14: left is {13}, which is less than 14. Good.
What we need to keep in mind is the condition is about entire subtrees, not just immediate children. See the below example, It is not a correct BST.
graph TD
M10((10)) --- M5((5))
M10 --- M15((15))
M5 --- M2((2))
M5 --- M12((12))
classDef bad fill:#c0392b,stroke:#922b21,color:#ffffff
class M12 bad
Look locally and everything seems fine: 2 < 5 < 12, and 5 < 10 < 15. But 12 sits in the left subtree of 10, and 12 is not less than 10. Search for 12 from the root and you go right (12 > 10) into {15}, and never find it. The node is in memory, reachable by traversal, and permanently invisible to search.
We can use the below function to check if a BST is valid or not.
public boolean isValidBST() {
return isValidRec(root, null, null);
}
private boolean isValidRec(Node node, Integer min, Integer max) {
if (node == null) return true;
if (min != null && node.data <= min) return false;
if (max != null && node.data >= max) return false;
return isValidRec(node.left, min, node.data)
&& isValidRec(node.right, node.data, max);
}At any node, the comparison we make does not just move one step down. It eliminates an entire subtree.
For an example, looking for 7:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
classDef path fill:#008987,stroke:#00605f,color:#ffffff
class N8,N3,N6,N7 path
Traversing the Tree
Traversal means visiting every node exactly once. There are four standard orders.
- In-order (left, node, right)
- Pre-order (node, left, right)
- Post-order (left, right, node)
- Level-order (top to bottom, left to right, using a queue)
Lets see how inOrder traversing work. We can implement it like this.
private void inOrder(Node node) {
if (node == null) return;
inOrder(node.left); // everything smaller
System.out.print(node.data + " "); // this node
inOrder(node.right); // everything larger
}Print everything smaller than the current node, then current node, and after all print everything larger than this node.
Searching a Binary Search Tree
This is simple. Start at the root and compare. Smaller means go left, larger means go right, equal means found, null means it is not here.
public boolean search(int value) {
return searchRec(root, value);
}
private boolean searchRec(Node node, int value) {
if (node == null) {
return false; // ran off the tree
}
if (value == node.data) {
return true; // found it
}
if (value < node.data) {
return searchRec(node.left, value); // Go to left
}
return searchRec(node.right, value); // Go to right
}Lets see an example where the key is 5.
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
N4 -.- NULL((N))
classDef path fill:#008987,stroke:#00605f,color:#ffffff
classDef nil fill:#ffffff,stroke:#c0392b,stroke-dasharray: 4 3,color:#c0392b
class N8,N3,N6,N4 path
class NULL nil
5 < 8 go left. 5 > 3 go right. 5 < 6 go left. 5 > 4 go right, which is null. Not present. Note that a failed search costs the same as a successful one down that path.
The iterative version
The recursion here is tail recursive, so it converts to a loop with no stack at all. Java does not eliminate tail calls, so this version genuinely saves memory on a deep tree:
public boolean searchIterative(int value) {
Node current = root;
while (current != null) {
if (value == current.data) return true;
current = (value < current.data) ? current.left : current.right;
}
return false;
}O(h) time, O(1) space. On a degenerate tree with a million nodes, the recursive version blows the stack and this one does not. Worth remembering.
Insertion
Insertion is search, with one twist: instead of reporting failure when you hit null, you put the new node there.
The reasoning is worth stating explicitly. The null you land on is the only place the value can legally go. Every comparison on the way down committed you to a side, and the position you arrive at is precisely the spot where a search for that value would have looked. Put the node there and future searches will find it.
Let's build the working tree from scratch by inserting 8, 3, 10, 1, 6, 14, 4, 7, 13, in that order.
Insert 8. Tree is empty, so 8 becomes the root.
graph TD
A((8))
Insert 3. 3 < 8, go left. Left is null. Place it.
graph TD
A((8)) ---B((3))
A -.- N((N))
Insert 10. 10 > 8, go right. Right is null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
Insert 1. 1 < 8 go left to 3. 1 < 3 go left, null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B -.- N((N))
Insert 6. 6 < 8 go left to 3. 6 > 3 go right, null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B --- E((6))
Insert 14. 14 > 8 go right to 10. 14 > 10 go right, null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B --- E((6))
C -.- N((N))
C --- F((14))
Insert 4. 4 < 8 left to 3. 4 > 3 right to 6. 4 < 6 left, null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B --- E((6))
C -.- N((N))
C --- F((14))
E --- G((4))
E -.- N2((N))
Insert 7. 7 < 8 left to 3. 7 > 3 right to 6. 7 > 6 right, null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B --- E((6))
C -.- N((N))
C --- F((14))
E --- G((4))
E --- H((7))
Insert 13. 13 > 8 right to 10. 13 > 10 right to 14. 13 < 14 left, null. Place it.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B --- E((6))
C -.- N((N))
C --- F((14))
E --- G((4))
E --- H((7))
F --- I((13))
F -.- N2((N))
Nine insertions, and we are back to the tree from the BST property section. Notice that every single insertion added a leaf. A BST insert never restructures anything that is already there, it only ever hangs a new node off a free slot. That is what makes insertion cheap, and it is also exactly why the tree's shape ends up at the mercy of the order the keys arrive in.
The code:
public void insert(int value) {
root = insertRec(root, value);
}
private Node insertRec(Node node, int value) {
if (node == null) {
return new Node(value); // found the empty slot
}
if (value < node.data) {
node.left = insertRec(node.left, value);
} else if (value > node.data) {
node.right = insertRec(node.right, value);
}
// value == node.data: duplicate, ignore
return node;
}Read that return statement carefully
This "return the subtree, reassign it to the parent" pattern is the idiom for the whole topic, and it is worth slowing down for.
insertRec returns the root of the subtree after the insertion. In the common case nothing changed, so it returns the same node it was given, and node.left = insertRec(node.left, ...) reassigns node.left to itself. Harmless. In the base case, it returns a brand new node, and that same assignment is what actually wires the new node into its parent.
Notice we never write code to track "the parent". The assignment on the way back up the recursion handles the relinking automatically. The same idiom does all the heavy lifting in deletion, so make sure it clicks here first.
Also note the top-level root = insertRec(root, value). Without it, inserting into an empty tree would create a node and immediately drop it on the floor, since Java passes references by value and reassigning the parameter inside the method changes nothing outside it.
Duplicates
The code above silently ignores duplicates. That is a design decision, not a law. Your options:
- Ignore them. The tree becomes a set. Simplest, and usually what you want.
- Count them. Add an
int countfield and increment it. The tree becomes a multiset, and this is the cleanest option when duplicates carry meaning. - Always send them one way. Use
<=so equal values go left. This works, but it means an exact-match search can no longer stop at the first hit if you need all of them, and it degrades the tree faster when there are many duplicates.
Pick one deliberately and document it. Silent inconsistency here is a genuine source of bugs.
Iterative insertion
public void insertIterative(int value) {
Node newNode = new Node(value);
if (root == null) {
root = newNode;
return;
}
Node current = root;
Node parent = null;
while (current != null) {
parent = current;
if (value < current.data) {
current = current.left;
} else if (value > current.data) {
current = current.right;
} else {
return; // duplicate
}
}
if (value < parent.data) parent.left = newNode;
else parent.right = newNode;
}Here you do have to track the parent by hand, which is exactly the bookkeeping the recursive version got for free. That trade, explicit pointers versus implicit stack, shows up in every tree algorithm you will write.
Minimum and Maximum
The BST property makes these trivial. Everything smaller is to the left, so the smallest value is as far left as you can go. Everything larger is to the right, so the largest is as far right as you can go.
graph TD
A((8)) --- B((3))
A --- C((10))
B --- D((1))
B --- E((6))
C -.- N1((N))
C --- H((14))
E --- F((4))
E --- G((7))
H --- I((13))
H -.- N2((N))
classDef minmax fill:#008987,stroke:#00605f,color:#ffffff
class D,H minmax
private Node findMinNode(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
private Node findMaxNode(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}A detail that catches people out: the minimum is not always a leaf. In our tree the minimum, 1, happens to be a leaf. But the leftmost node can still have a right child. What it cannot have is a left child, because then it would not be leftmost. That single fact is what makes deletion Case 3 work, so hold onto it.
Both run in O(h).
In-order Successor and Predecessor
The in-order successor of a node is the next-largest key in the tree, that is, the node that comes immediately after it in a sorted traversal. You need this for deletion, and it is also how iterators over a TreeMap advance.
There are two cases:
Case A: the node has a right subtree. The successor is the minimum of that right subtree. Everything in the right subtree is larger than the node, so the smallest of them is the next one up.
For node 8, the right subtree is {10, 13, 14}, and its minimum is 10. So the successor of 8 is 10:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
classDef target fill:#008987,stroke:#00605f,color:#ffffff
classDef succ fill:#e67e22,stroke:#b35c0c,color:#ffffff
class N8 target
class N10 succ
Case B: no right subtree. Then the successor is the lowest ancestor for which the node lies in the left subtree. Walk down from the root, and every time you go left, remember the node you came from. That last remembered node is the successor.
For node 7, there is no right child. Walking down from the root: at 8 we go left (record 8), at 3 we go right, at 6 we go right, arrive at 7. The last node we went left from is 8, so the successor of 7 is 8. Check it against the sorted order 1 3 4 6 7 8 10 13 14, and 8 does indeed follow 7.
The two cases are useful for understanding, but you do not need to branch on them in code. A single walk from the root handles both: remember the last node you turned left at, and if the key has a right subtree the walk naturally ends up at its minimum anyway.
public Integer successor(int value) {
Node current = root;
Node candidate = null;
while (current != null) {
if (value < current.data) {
candidate = current; // current is a possible successor
current = current.left;
} else {
current = current.right; // current is too small, look right
}
}
return candidate == null ? null : candidate.data;
}The predecessor is the exact mirror: maximum of the left subtree if one exists, otherwise the lowest ancestor whose right subtree contains the node.
Deletion
Deletion is the hard one, because removing a node leaves a hole and the tree has to close it without violating the BST property. There are three cases, in increasing difficulty.
Case 1: the node is a leaf
No children, nothing depends on it. Detach it.
Delete 1 from our tree:
Before:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
classDef doomed fill:#c0392b,stroke:#922b21,color:#ffffff
class N1 doomed
After:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 -.- NC((N))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
Set the parent's pointer to null and the node is gone. In our recursive style, we just return null and the parent's assignment does the rest.
Case 2: the node has exactly one child
Promote the child. The child's entire subtree already sits on the correct side of every ancestor, so splicing it up one level breaks nothing.
Delete 14, which has only a left child (13):
Before:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
classDef doomed fill:#c0392b,stroke:#922b21,color:#ffffff
class N14 doomed
After:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N13((13))
N6 --- N4((4))
N6 --- N7((7))
Node 10's right pointer now goes straight to 13. Why is this safe? Because 13 was already in 10's right subtree, so 13 > 10 was already guaranteed. Moving it up one level does not change which side of 10 it is on, and it does not change its relationship to any other ancestor either.
Note that the child gets promoted regardless of whether it was a left or right child. Deleting 14 promoted its left child into 10's right slot. That looks wrong for half a second and is completely correct.
Case 3: the node has two children
Now you cannot just remove it, because you have two subtrees and only one slot to hang them from.
The trick is not to remove the node at all. Instead, overwrite its value with a value that is legal in that position, then delete that value from where it used to live.
Which value is legal? Only two candidates work:
- the in-order successor: the smallest value in the right subtree, or
- the in-order predecessor: the largest value in the left subtree.
Take the successor. It is larger than everything in the left subtree, because it lives in the right subtree and everything there beats everything on the left. And it is smaller than everything else in the right subtree, because it is the minimum of that subtree. So it slots into the deleted node's position perfectly. It is, quite literally, the value that sits next to the deleted one in sorted order, which is why nothing around it needs to move.
Delete 3, which has children 1 and 6:
Before:
graph TD
N8((8)) --- N3((3))
N8 --- N10((10))
N3 --- N1((1))
N3 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 --- N4((4))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
classDef doomed fill:#c0392b,stroke:#922b21,color:#ffffff
classDef succ fill:#e67e22,stroke:#b35c0c,color:#ffffff
class N3 doomed
class N4 succ
Step 1: find the in-order successor of 3. Go right once to 6, then as far left as possible: 6 has a left child 4, and 4 has no left child. So the successor is 4.
Step 2: overwrite 3 with 4.
Step 3: delete the original 4 from the right subtree. It was a leaf, so that is Case 1.
After:
graph TD
N8((8)) --- N4((4))
N8 --- N10((10))
N4 --- N1((1))
N4 --- N6((6))
N10 -.- NA((N))
N10 --- N14((14))
N6 -.- ND((N))
N6 --- N7((7))
N14 --- N13((13))
N14 -.- NB((N))
Check the invariant: 1 < 4, and the right subtree of 4 is {6, 7}, both greater than 4. Everything under 4 is still less than 8. Valid.
Why Case 3 always terminates
The recursive delete in Case 3 looks alarming: deletion calls deletion. But it can never recurse more than one extra level deep, and the reason is the fact I flagged earlier.
The successor is the leftmost node of the right subtree. Leftmost means it has no left child. A node with no left child has either zero children or one (a right child). So deleting the successor always lands in Case 1 or Case 2, never Case 3. The recursion goes exactly one step further and stops.
The code
public void delete(int value) {
root = deleteRec(root, value);
}
private Node deleteRec(Node node, int value) {
if (node == null) {
return null; // value not in the tree
}
if (value < node.data) {
node.left = deleteRec(node.left, value);
} else if (value > node.data) {
node.right = deleteRec(node.right, value);
} else {
// this is the node to remove
// Case 1 and Case 2 collapse into two lines:
// if there is no left child, promote the right (which may be null)
if (node.left == null) return node.right;
// if there is no right child, promote the left
if (node.right == null) return node.left;
// Case 3: two children
int successorValue = findMinNode(node.right).data;
node.data = successorValue;
node.right = deleteRec(node.right, successorValue);
}
return node;
}Two things worth noticing.
Cases 1 and 2 collapse. A leaf has node.left == null, so it returns node.right, which is also null. That is exactly the leaf behaviour. You do not need a separate branch for the leaf case, and writing one is a common way to add a bug.
Case 3 does not delete a node, it deletes a value. We overwrite node.data and then recurse into the right subtree to remove the duplicate. The Node object at that position is the same object it always was.
A subtlety: always taking the successor is slightly harmful
This algorithm, always promoting the in-order successor, is called Hibbard deletion. It is correct, and it is what almost every textbook shows.
It is also asymmetric, and that asymmetry accumulates. Every deletion pulls a node out of the right subtree and never out of the left, so over many random insert/delete cycles the tree drifts left-heavy. The classic analysis showed that after enough random insert/delete pairs, expected height degrades toward O(sqrt(n)) rather than staying at O(log n).
The practical fix is one line: pick the successor or the predecessor at random, or alternate. In production you would use a self-balancing tree anyway, which sidesteps the issue entirely. But it is a good example of how a "correct" algorithm can still be quietly wrong over time.
Why Every BST Operation Is O(h)
Look back at search, insert, min, max, successor, and delete. Every one of them does the same thing: start at the root and walk downward, one level per comparison, until it hits a leaf or a null.
None of them ever backtracks. None of them visits a sibling. So the work is bounded by the number of levels, which is the height h. That gives O(h) for all of them.
That is the whole story, and it means the interesting question is not "how fast is a BST" but "how tall is this particular tree".
If the tree is balanced, h ≈ log2(n) and everything is O(log n). If it is degenerate, h = n - 1 and everything is O(n).
graph TD
R((8)) --- L1((4))
R --- R1((12))
L1 --- L2((2))
L1 --- L3((6))
R1 --- R2((10))
R1 --- R3((14))
Seven nodes, height 2, three comparisons worst case. Compare that with the same seven values inserted in sorted order, coming up next.
Balanced vs Degenerate: Insertion Order Decides Everything
Here is the catch that makes plain BSTs unsuitable for production, and it is not subtle.
Insert 2, 4, 6, 8, 10, 12, 14 in that order. Every value is larger than everything already in the tree, so every insertion goes right, forever:
graph TD
A((2)) -.- NA((N))
A --- B((4))
B -.- NB((N))
B --- C((6))
C -.- NC((N))
C --- D((8))
D -.- ND((N))
D --- E((10))
E -.- NE((N))
E --- F((12))
F -.- NF((N))
F --- G((14))
Same seven values. Same code. Height 6 instead of 2. Searching for 14 now takes seven comparisons instead of three, and the gap widens without bound as n grows.
This is technically still a valid BST. Every node satisfies the property. It has simply degenerated into a singly linked list with a wasted pointer per node, and it has lost every advantage that motivated using a tree.
| Tree shape | Height | Search / insert / delete |
|---|---|---|
| Perfect | log2(n) |
O(log n) |
| Randomly built | ~1.39 log2(n) average depth |
O(log n) |
| Degenerate | n - 1 |
O(n) |
How often does this actually happen?
More often than you would like, because sorted input is the normal case, not the pathological one.
- Reading rows out of a database that came back
ORDER BY id - Loading timestamps from a log file
- Replaying an append-only event stream
- Rebuilding an index from a sorted dump
- Auto-incrementing primary keys, ever
In every one of those, a naive BST silently turns into a linked list. It does not crash. It does not warn you. It just gets slower and slower as the dataset grows, and the failure shows up in production under load rather than in your test with twelve elements.
The good news, if you can get it: for keys arriving in random order, a BST is fine. The expected number of comparisons for a search is about 1.39 log2(n), only 39% worse than a perfectly balanced tree, and the expected height is around 3 log2(n). Randomness gives balance for free. The problem is that real data is very rarely random.
One practical mitigation, if you control the load: shuffle before bulk-inserting. It costs O(n) and converts the worst case into the average case. If you do not control the input order, you need a tree that fixes itself.
Self-Balancing Trees
Everything so far has a single weakness: the tree has no opinion about its own shape. It accepts whatever the insertion order hands it.
A self-balancing BST fixes that. After every insertion and deletion it checks whether it has become lopsided, and if so it restructures itself. The guarantee upgrades from "O(log n) if you are lucky with your input" to "O(log n), always".
There is exactly one primitive that makes this possible.
Rotations: the one primitive
A rotation changes the shape of a subtree while leaving its in-order sequence untouched. That second half is the important part: because the in-order sequence is preserved, the BST property survives automatically, and no search that worked before the rotation stops working after it.
Here is a left rotation around x. Read T1, T2, T3 as entire subtrees, possibly empty:
Before:
graph TD
X((x)) --- T1[T1]
X --- Y((y))
Y --- T2[T2]
Y --- T3[T3]
After:
graph TD
Y((y)) --- X((x))
Y --- T3[T3]
X --- T1[T1]
X --- T2[T2]
y moves up, x moves down and to the left, and T2 (which was y's left subtree) becomes x's right subtree. That reassignment of T2 is the only fiddly part, and it is the step people get wrong.
Read the in-order sequence off both diagrams:
- Before:
T1, x, T2, y, T3 - After:
T1, x, T2, y, T3
Identical. That is the whole trick. T2 sits between x and y in sorted order both before and after, so hanging it off x's right instead of y's left is legal.
A right rotation is the exact mirror, and it is what you use on a left-heavy subtree.
// Left rotation: the right child becomes the new subtree root.
private Node rotateLeft(Node x) {
Node y = x.right;
Node t2 = y.left;
y.left = x; // x drops under y
x.right = t2; // y's old left subtree becomes x's right subtree
updateHeight(x); // x is now lower, so update it first
updateHeight(y);
return y; // y is the new root of this subtree
}
// Right rotation: the left child becomes the new subtree root.
private Node rotateRight(Node y) {
Node x = y.left;
Node t2 = x.right;
x.right = y;
y.left = t2;
updateHeight(y);
updateHeight(x);
return x;
}Six pointer writes and two height updates. A rotation is O(1) — it does not touch the subtrees at all, only the two nodes at the top. That is why rebalancing stays cheap.
Note the order of the height updates: x ends up below y, so x's height has to be recomputed before y's can be correct.
Everything from here on is just a policy layered on top of this one operation: when do we rotate, and where.
AVL Trees
An AVL tree (Adelson-Velsky and Landis, 1962, the first self-balancing BST ever invented) enforces the strictest sensible rule:
For every node, the heights of its left and right subtrees differ by at most 1.
The balance factor
Each node stores its own height, and from that we derive its balance factor:
balanceFactor(node) = height(node.left) - height(node.right)Legal values are -1, 0, +1. Anything outside that range means the node is unbalanced and needs fixing. A positive factor means left-heavy, negative means right-heavy.
private int height(Node n) {
return n == null ? -1 : n.height; // empty subtree has height -1
}
private int balanceFactor(Node n) {
return n == null ? 0 : height(n.left) - height(n.right);
}
private void updateHeight(Node n) {
n.height = 1 + Math.max(height(n.left), height(n.right));
}Storing the height on each node is what keeps this cheap. Recomputing a height by walking the subtree would be O(n); reading a cached field is O(1), and after a rotation only two nodes need updating.
The four cases
An insertion can push exactly one node out of balance in exactly four ways, depending on where the new node landed relative to the unbalanced node. All four examples below insert three keys and end at the same place: 20 at the root with 10 and 30 as children.
Case LL: left child, left subtree
Insert 30, 20, 10. The balance factor of 30 becomes +2, and the new key went into the left subtree of its left child.
graph TD
A((30)) --- B((20))
A -.- N1((N))
B --- C((10))
B -.- N2((N))
One right rotation around 30:
graph TD
B((20)) --- C((10))
B --- A((30))
Case RR: right child, right subtree
Insert 10, 20, 30. The mirror image. Balance factor of 10 becomes -2.
graph TD
A((10)) -.- N1((N))
A --- B((20))
B -.- N2((N))
B --- C((30))
One left rotation around 10 gives the same balanced result.
Case LR: left child, right subtree
Insert 30, 10, 20. Now a single rotation is not enough, because the offending node is on the inside of the bend.
graph TD
A((30)) --- B((10))
A -.- N1((N))
B -.- N2((N))
B --- C((20))
Step 1, left rotation around 10, which straightens the zig-zag into a straight line and turns this into Case LL:
graph TD
A((30)) --- C((20))
A -.- N1((N))
C --- B((10))
C -.- N2((N))
Step 2, right rotation around 30:
graph TD
C((20)) --- B((10))
C --- A((30))
Case RL: right child, left subtree
Insert 10, 30, 20. The mirror of LR.
graph TD
A((10)) -.- N1((N))
A --- B((30))
B --- C((20))
B -.- N2((N))
Right rotation around 30, then left rotation around 10.
The pattern is worth stating plainly: if the imbalance goes straight (LL or RR), one rotation. If it zig-zags (LR or RL), rotate the child first to straighten it, then rotate the parent.
Insertion with rebalancing
The insert is the plain BST insert with a rebalance step bolted onto the way back up the recursion:
private Node insertRec(Node node, int value) {
// 1. Ordinary BST insertion
if (node == null) return new Node(value);
if (value < node.data) node.left = insertRec(node.left, value);
else if (value > node.data) node.right = insertRec(node.right, value);
else return node; // duplicate, nothing changed
// 2. This node may have grown taller, so refresh its height
updateHeight(node);
// 3. Rebalance if the insertion broke the invariant here
int bf = balanceFactor(node);
if (bf > 1 && value < node.left.data) // LL
return rotateRight(node);
if (bf < -1 && value > node.right.data) // RR
return rotateLeft(node);
if (bf > 1 && value > node.left.data) { // LR
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (bf < -1 && value < node.right.data) { // RL
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}This is the same "return the subtree, reassign it to the parent" idiom from the plain BST insert, doing even more work for us now. When a rotation changes which node sits at the top of a subtree, returning the new root is exactly how the parent gets relinked. No parent pointers required.
An AVL insertion needs at most one rebalance. Once you rotate, the subtree's height returns to what it was before the insertion, so every ancestor above it is automatically fine again. The recursion still unwinds to the root, but it does no more rotating.
Deletion
Deletion reuses the BST deletion you already know, with the same rebalance step appended. There is one real difference, and it catches people out.
On insert, we could work out which case we were in by comparing the inserted value against the child. On delete, there is no inserted value to compare against — the imbalance is caused by a subtree getting shorter, somewhere else. So we detect the case by looking at the child's own balance factor instead:
private Node deleteRec(Node node, int value) {
if (node == null) return null;
if (value < node.data) {
node.left = deleteRec(node.left, value);
} else if (value > node.data) {
node.right = deleteRec(node.right, value);
} else {
if (node.left == null) return node.right; // 0 or 1 child
if (node.right == null) return node.left;
Node s = node.right; // in-order successor
while (s.left != null) s = s.left;
node.data = s.data;
node.right = deleteRec(node.right, s.data);
}
updateHeight(node);
int bf = balanceFactor(node);
// Case detection now reads the child's balance factor, not an inserted key
if (bf > 1 && balanceFactor(node.left) >= 0) return rotateRight(node); // LL
if (bf > 1) { // LR
node.left = rotateLeft(node.left);
return rotateRight(node);
}
if (bf < -1 && balanceFactor(node.right) <= 0) return rotateLeft(node); // RR
if (bf < -1) { // RL
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}The other difference: a deletion can require up to O(log n) rotations. Unlike insertion, rebalancing one subtree after a delete can leave it shorter than it was, which can unbalance its parent, and so on all the way to the root. It is still O(log n) overall, since each rotation is O(1) and there are at most h of them.
The height guarantee
Why does "differ by at most 1" force logarithmic height? Ask the opposite question: what is the fewest nodes an AVL tree of height h can have? That is the worst case, the most stretched-out an AVL tree is allowed to be.
N(0) = 1 a single node
N(1) = 2 a root with one child
N(h) = 1 + N(h-1) + N(h-2) root, plus the tallest legal pair of subtreesThe tallest legal subtree pair is one of height h-1 and one of height h-2 — the AVL rule forbids a bigger gap. That recurrence is the Fibonacci sequence in disguise, which grows exponentially, so N(h) grows exponentially in h. Inverting it gives:
h < 1.44 * log2(n + 2)An AVL tree is never more than about 44% taller than a perfect binary tree. That bound is tight and it holds no matter what order the keys arrive in.
Sorted input, revisited
Remember what sorted insertion did to the plain BST. Here is the same input into an AVL tree, from the implementation at the end of this post:
1..15 inserted in sorted order
Plain BST height: 14 (a linked list)
AVL tree height: 3 (a perfect tree)
100,000 sorted inserts
Plain BST height: 99,999
AVL tree height: 16 (bound: 1.44 * log2(100002) = 23.9)The pathological input produces a perfect tree. Every insertion that would have extended the stick triggered a rotation that folded it back down. That is the entire value proposition.
Red-Black Trees
Red-black trees reach the same O(log n) guarantee by a completely different route. Instead of tracking heights numerically, every node carries a single bit of colour, and a handful of colour rules do the work.
The payoff for the looser bookkeeping is fewer rotations on writes, which is why red-black trees, not AVL trees, are what standard libraries ship.
The five rules
- Every node is either red or black.
- The root is black.
- Every NIL leaf is black. (Every missing child counts as a black "leaf" node, which is why colour arguments always work out evenly.)
- A red node's children are both black. Equivalently: no two reds in a row on any path.
- Every path from a node down to any of its descendant NILs contains the same number of black nodes.
Rules 4 and 5 are the ones doing the work. Everything else is bookkeeping.
Here is a real red-black tree, produced by inserting 10, 20, 30, 15, 25, 5, 1 into the implementation below:
graph TD
N20((20)) --- N10((10))
N20 --- N30((30))
N10 --- N5((5))
N10 --- N15((15))
N5 --- N1((1))
N5 -.- NA((N))
N30 --- N25((25))
N30 -.- NB((N))
classDef red fill:#c0392b,stroke:#7b241c,color:#ffffff
classDef black fill:#2c3e50,stroke:#1b2631,color:#ffffff
class N10,N1,N25 red
class N20,N5,N15,N30 black
Walk the rules: root 20 is black. No red node has a red child (10 is red, its children 5 and 15 are both black; 1 and 25 are red leaves with only NIL children). And every root-to-NIL path passes through exactly two black nodes, counting the black NIL at the end but not the root itself. Check a couple: 20 → 10 → 5 → 1 → NIL hits 5 and NIL. 20 → 30 → NIL hits 30 and NIL. Both 2.
Black height, and why the height is bounded
The black height of a node is the number of black nodes on any path from it down to a NIL, not counting the node itself. Rule 5 is what makes "any path" meaningful — they all give the same answer.
Now the bound falls out in two lines:
- The shortest possible root-to-NIL path is all black. Its length is the black height,
bh. - The longest possible path alternates red and black, because rule 4 forbids two reds in a row. It cannot be longer than
2 * bh.
So the longest path is at most twice the shortest, which gives:
h <= 2 * log2(n + 1)That is looser than AVL's 1.44 log2(n) — a red-black tree can be about 40% taller than an AVL tree holding the same keys. It is still O(log n), which is all the complexity guarantee needs.
Insertion: recolour when you can, rotate when you must
A new node is always inserted red. That choice is deliberate: adding a red node never breaks rule 5, because it does not change any path's black count. The only rule it can break is rule 4, a red node under a red parent.
So insertion becomes: place the node, then fix red-red violations on the way up. Which fix you apply depends entirely on the colour of the new node's uncle (the parent's sibling).
Case 1: the uncle is red. No rotation needed at all. Recolour the parent and uncle black, and the grandparent red. The black count on every path through this subtree is unchanged, and the red-red violation is gone — but the grandparent is now red, so it might clash with its parent. Move up two levels and repeat.
graph TD
G((G)) --- P((P))
G --- U((U))
P --- X((X))
P -.- N1((N))
classDef red fill:#c0392b,stroke:#7b241c,color:#ffffff
classDef black fill:#2c3e50,stroke:#1b2631,color:#ffffff
class P,U,X red
class G black
becomes:
graph TD
G((G)) --- P((P))
G --- U((U))
P --- X((X))
P -.- N1((N))
classDef red fill:#c0392b,stroke:#7b241c,color:#ffffff
classDef black fill:#2c3e50,stroke:#1b2631,color:#ffffff
class G,X red
class P,U black
Case 2: the uncle is black, and the new node is an inner grandchild (left child's right child, or right child's left child). Rotate the parent to straighten the zig-zag. This does not fix anything by itself, it just converts the situation into Case 3. Exactly the same manoeuvre as the AVL LR and RL cases.
Case 3: the uncle is black, and the new node is an outer grandchild. Recolour the parent black and the grandparent red, then rotate the grandparent. This is terminal — after it, the loop ends.
The critical property: Case 1 is the only one that repeats, and it moves two levels up each time, so it runs at most h/2 times. Cases 2 and 3 happen at most once each, at the very end. That gives at most 2 rotations per insertion, no matter how big the tree is.
The code
class RBNode {
int data;
boolean red = true; // new nodes start red
RBNode left, right, parent;
RBNode(int data) { this.data = data; }
}
public class RedBlackTree {
private RBNode root;
private boolean isRed(RBNode n) {
return n != null && n.red; // a null child is a black NIL
}
public void insert(int value) {
RBNode parent = null;
RBNode current = root;
while (current != null) { // ordinary BST descent
parent = current;
if (value < current.data) current = current.left;
else if (value > current.data) current = current.right;
else return; // duplicate
}
RBNode node = new RBNode(value);
node.parent = parent;
if (parent == null) root = node;
else if (value < parent.data) parent.left = node;
else parent.right = node;
fixAfterInsert(node);
}
private void fixAfterInsert(RBNode node) {
// Keep going while there is a red-red violation to repair.
while (node != root && isRed(node.parent)) {
RBNode parent = node.parent;
RBNode grand = parent.parent;
if (parent == grand.left) {
RBNode uncle = grand.right;
if (isRed(uncle)) { // Case 1: recolour, move up
parent.red = false;
uncle.red = false;
grand.red = true;
node = grand;
} else {
if (node == parent.right) { // Case 2: straighten first
node = parent;
rotateLeft(node);
parent = node.parent;
}
parent.red = false; // Case 3: recolour and rotate
grand.red = true;
rotateRight(grand);
}
} else { // mirror image
RBNode uncle = grand.left;
if (isRed(uncle)) {
parent.red = false;
uncle.red = false;
grand.red = true;
node = grand;
} else {
if (node == parent.left) {
node = parent;
rotateRight(node);
parent = node.parent;
}
parent.red = false;
grand.red = true;
rotateLeft(grand);
}
}
}
root.red = false; // rule 2. Always safe: it never breaks rule 5.
}
// Rotations are the same as AVL's, except they maintain parent links
// and have to re-point the root when the subtree root changes.
private void rotateLeft(RBNode x) {
RBNode y = x.right;
x.right = y.left;
if (y.left != null) y.left.parent = x;
y.parent = x.parent;
if (x.parent == null) root = y;
else if (x == x.parent.left) x.parent.left = y;
else x.parent.right = y;
y.left = x;
x.parent = y;
}
private void rotateRight(RBNode y) {
RBNode x = y.left;
y.left = x.right;
if (x.right != null) x.right.parent = y;
x.parent = y.parent;
if (y.parent == null) root = x;
else if (y == y.parent.right) y.parent.right = x;
else y.parent.left = x;
x.right = y;
y.parent = x;
}
public boolean contains(int value) {
RBNode c = root;
while (c != null) {
if (value == c.data) return true;
c = value < c.data ? c.left : c.right;
}
return false;
}
}Note that contains is completely untouched by the colours. Reading a red-black tree is just reading a BST. The colours only ever matter during writes, which is a good thing to internalise: all this machinery is invisible to the common case.
Also notice the last line of the fixup, root.red = false. Forcing the root black can never violate rule 5, because the root is on every path, so it adds one to every path's black count equally. That is why it is safe to do unconditionally.
Deletion
Deletion is genuinely harder than insertion, and I am going to describe it rather than print it.
The difficulty: removing a black node reduces the black count on every path through it, breaking rule 5. The standard fix introduces the idea of a "doubly black" node — a placeholder carrying one unit of black debt — and then pushes that debt up the tree until it can be discharged, either by finding a red node to absorb it or by reaching the root. There are four cases, each with a mirror, so eight branches in total.
It is still at most 3 rotations and O(log n) work. But it is around 100 lines of dense pointer manipulation with very little intuition to hold onto, and it is the single most bug-prone thing in this entire topic.
The honest engineering advice: use java.util.TreeMap. It is a battle-tested red-black tree that has been exercised by millions of programs. Writing your own red-black delete is an excellent exercise and an inadvisable production decision.
Sorted input, revisited
The same test as before, from the implementation above:
1..15 inserted in sorted order
Plain BST height: 14
Red-black height: 5
AVL height: 3
100,000 sorted inserts
Plain BST height: 99,999
Red-black height: 30 (bound: 2 * log2(100001) = 33.2)
AVL height: 16 (bound: 1.44 * log2(100002) = 23.9)Both self-balancing trees kill the pathology. The AVL tree is visibly tighter, exactly as the two bounds predict.
AVL vs Red-Black: Which One
They solve the same problem with a different trade-off, and the trade-off is read speed versus write speed.
| AVL | Red-Black | |
|---|---|---|
| Balance rule | height difference at most 1 | no two reds in a row, equal black counts |
| Height bound | 1.44 log2(n) |
2 log2(n) |
| Extra storage per node | an int height (or 2 bits) | 1 bit of colour |
| Lookup | faster, the tree is shorter | slightly slower |
| Rotations per insert | at most 2 | at most 2 |
| Rotations per delete | up to O(log n) | at most 3 |
| Recolouring | n/a | up to O(log n), but O(1) amortised |
| Best for | read-heavy workloads | write-heavy or mixed workloads |
The decisive line is rotations per delete. AVL's stricter invariant means a single deletion can cascade rotations all the way to the root. Red-black's looser invariant absorbs most of that with cheap recolouring instead, and recolouring is just a bit flip — no pointer writes, and far friendlier to a CPU cache.
Why the standard libraries chose red-black
- Java:
TreeMapandTreeSetare red-black trees.HashMapalso converts a bucket to a red-black tree once it holds 8 or more colliding entries, which caps worst-case lookup within a bucket at O(log n) instead of O(n) — a direct mitigation against hash-collision denial-of-service attacks. - C++:
std::map,std::set,std::multimap,std::multisetare all red-black in every major implementation. - Linux kernel: red-black trees are everywhere — the completely fair scheduler's runqueue, virtual memory area lookup,
epoll's watch set, ext3/ext4 directory indexing.
The common thread is that these are general-purpose containers facing unknown, mixed workloads. Predictable, cheap writes matter more than squeezing out the last bit of lookup speed. AVL trees remain the better choice when you build once and read many times.
In practice you will use a library implementation of one of these far more often than you will write one. The reason to understand them is to know why TreeMap costs O(log n) instead of HashMap's O(1), and when that trade is worth making: when you need keys in order.
Beyond Binary: B-Trees
One more branch of the family, because it is the one actually holding your data.
A B-tree drops the binary restriction. Each node holds many keys (often hundreds) and has many children. A node with k keys has k + 1 children, and the keys act as separators: everything in child i falls between key i-1 and key i.
Why bother? Because the cost model changes when the tree does not fit in memory. Reading one 4KB page from an SSD costs roughly the same as reading 8 bytes from it — the expensive part is the round trip, not the volume. A binary tree over 100 million rows is about 27 levels deep, so 27 round trips. A B-tree with 200 keys per node is 4 levels deep. Four round trips instead of twenty-seven.
That is why every relational database index, and essentially every filesystem (NTFS, ext4, HFS+, Btrfs), is a B-tree or a B+ tree. The BST logic you have learned is exactly right; only the branching factor changes, chosen to match the hardware's page size.
Gotchas Worth Knowing
Recursion depth. Recursive operations use O(h) stack. On a balanced tree that is ~20 frames for a million nodes. On a degenerate plain BST it is a million frames and a StackOverflowError. If input might be sorted and you cannot use a balanced tree, go iterative.
Never mutate a key while it is in the tree. The node's position was decided by comparisons made at insertion time. Change the key and the node sits somewhere search will never look. It is still in memory, still reachable by traversal, and permanently unfindable. Remove, change, reinsert.
Your comparator must be a total order. If compare(a, b) is inconsistent or non-transitive, or disagrees with equals, behaviour is undefined in ways that are miserable to debug. This is a real source of bugs when a class implements Comparable carelessly.
A BST is not a heap. Both are binary trees and they are otherwise unrelated. A BST orders left-to-right, giving sorted traversal and O(log n) search for any key. A heap orders parent-to-child only, giving O(1) access to the minimum and nothing else — searching a heap for an arbitrary value is O(n).
Do not delete during a traversal. Same rule as mutating a collection while iterating it. Collect first, then remove.
Reach for a BST when you need order. For exact-match lookup alone, a hash table is faster. Range queries, floor, ceiling, rank, select, sorted iteration, nearest-neighbour — none of those are possible with a hash table, and all of them fall out of the BST property for free.
The single most valuable thing to carry forward: a BST's performance is a property of its shape, and its shape is a property of its insertion order. AVL trees break that dependency with heights and rotations. Red-black trees break it with colours and fewer rotations. Everything else in the balanced-tree literature is a variation on that one idea.
