DSA · Lesson 8 of 20 · 4 min
Introduction to Trees: Binary Trees & BSTs
You need to explain why a BST is faster than an array for dynamic data, and what can make it just as slow.
After this, you'll be able to explain the trade-offs of using a tree, implement a Binary Search Tree, and spot the most common BST interview trap. Trees model hierarchical data, which you work with daily in the DOM and component trees. Knowing how to manipulate them is not an abstract exercise.
What makes a tree a tree?
A tree is just nodes connected in a parent-child relationship. The top node is the root. Nodes with no children are leaf nodes. That's it. Unlike an array, a tree is non-linear, which allows for more complex relationships and, in the right structure, faster operations.
The most common tree you'll see in interviews is a Binary Tree.
A Binary Tree is a tree where each node has at most two children: a left child and a right child. It's a simple constraint, but it's the foundation for more powerful structures.
The Binary Search Tree (BST) property
A Binary Search Tree is a binary tree with one extra rule that changes everything. For any given node:
- All values in its left subtree are less than the node's value.
- All values in its right subtree are greater than the node's value.
- Both its left and right subtrees must also be binary search trees.
This ordering property is the whole point. It lets you discard half the tree at every step of a search, just like binary search on a sorted array. This is what gives a BST its average-case O(log n) time complexity for search, insertion, and deletion.
This structure is ideal when you need to store sorted data that changes often. A sorted array has O(log n) search, but insertion or deletion is O(n) because you have to shift elements. A BST handles all three in O(log n) on average.
How to implement a basic BST
You need a TreeNode class and a class for the tree itself. The insert and search methods demonstrate the core logic: at each node, decide whether to go left or right.
This implementation is iterative. You can also write it recursively, but the logic is the same. An interviewer might ask you to switch between the two.
class TreeNode<T> {
value: T;
left: TreeNode<T> | null;
right: TreeNode<T> | null;
constructor(value: T) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree<T> {
root: TreeNode<T> | null;
constructor() {
this.root = null;
}
insert(value: T): void {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return;
}
let currentNode = this.root;
while (true) {
if (value === currentNode.value) return; // Ignore duplicates
if (value < currentNode.value) {
if (currentNode.left === null) {
currentNode.left = newNode;
return;
}
currentNode = currentNode.left;
} else {
if (currentNode.right === null) {
currentNode.right = newNode;
return;
}
currentNode = currentNode.right;
}
}
}
search(value: T): TreeNode<T> | null {
let currentNode = this.root;
while (currentNode !== null) {
if (value === currentNode.value) {
return currentNode;
} else if (value < currentNode.value) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
return null;
}
}
The catch: When O(log n) becomes O(n)
The O(log n) performance of a BST depends on the tree being reasonably balanced. If you insert elements in sorted order (e.g., 1, 2, 3, 4, 5), you don't get a bushy tree. You get a skewed, degenerate chain of nodes.
This is effectively a linked list.
Searching this tree is O(n). You have to visit every node to find the last element. This is the worst-case scenario for a BST and a critical point to mention in an interview. It shows you understand the trade-offs.
How to answer: "A BST provides O(log n) average time for search, insert, and delete. However, in the worst case, such as when inserting pre-sorted data, it can become unbalanced and degrade to O(n). To guarantee O(log n) performance, we would use a self-balancing BST like an AVL tree or a Red-Black tree."
You are not expected to implement a self-balancing tree in most frontend interviews, but you are expected to know they exist and why.
The classic "Is Valid BST?" trap
A very common interview question is to write a function isValidBST(root) that returns true if a given binary tree is a valid BST.
The trap: It's tempting to write a function that checks if node.left.value < node.value and node.right.value > node.value for every node. This is wrong.
This check is local. It doesn't ensure that all nodes in the left subtree are less than the current node, only the immediate child. For example, a right child of a left node could be larger than the root, violating the BST property.
The solution: You must pass down constraints. As you traverse the tree, you keep track of the valid range (minimum and maximum allowed values) for each node.
- When you go left from a node, you update the
maxallowed value to be that node's value. - When you go right, you update the
minallowed value.
If any node's value falls outside its allowed range, the tree is not a valid BST. This is a problem you should practice on a platform like /problems/validate-binary-search-tree/.
Try it
Add a findMin() method to the BinarySearchTree class. It should find the node with the smallest value. Because of the BST property, you don't need to check every node. The implementation should be just a few lines of code.
Next: We will cover the fundamental ways to visit every node in a tree in "Tree Traversal Algorithms (BFS & DFS)".
Lock it in — apply this lesson under interview conditions.