EdTech

3 · Trees · Data Structures

Binary Search Trees

·

Binary Search Trees: Core Idea

A binary search tree (BST) is a binary tree in which each node stores a key and the keys in its left and right subtrees are constrained relative to that node’s key. This ordering structure distinguishes a BST from a general binary tree.

A BST is useful when data should be organized according to comparisons between keys. The ordering rule applies at every node, so each subtree must itself satisfy the BST property.

How the Ordering Constraint Organizes Keys

For any node, the keys in one subtree belong on one side of the node’s key in the chosen ordering, and the keys in the other subtree belong on the other side. A comparison operation determines which subtree is relevant when following the ordering.

For example, suppose a node contains the key 50. A key that compares as belonging on the first side of 50 must be placed in the corresponding subtree; a key that belongs on the other side must be placed in the other subtree. The same decision is repeated at the next node.

The precise inequality symbols and the policy for equal keys must be defined by an implementation or course convention. Do not assume a duplicate-key rule unless one is explicitly specified.

Tree Shape and Balance

The ordering constraint alone does not guarantee that a BST has a balanced shape. An ordinary BST may become unbalanced, with many nodes concentrated along a long path.

Tree type Shape guarantee from the supplied material
Ordinary BST May be unbalanced
AVL tree A balanced tree type
Red-black tree A balanced tree type

Balance concerns the shape of the tree. BST ordering concerns how keys are constrained relative to nodes. These are related design concerns, but they are not the same property.

Inorder Traversal

Inorder traversal visits a node’s subtrees and node in this recursive order:

  1. Traverse the first subtree.
  2. Visit the current node.
  3. Traverse the second subtree.

Because inorder traversal visits every node once, its time for a BST with n nodes is:

[ T(n) = O(n) ]

This remains O(n) whether the BST is balanced or unbalanced: a full traversal still has to visit all n nodes.

Comparator-Based BST Traversal Outline

The following TypeScript outline represents a node and performs recursive inorder traversal. The traversal does not need to decide how equal keys are stored, because it only visits the existing structure.

type Node<T> = {
  key: T;
  left: Node<T> | null;
  right: Node<T> | null;
};

function inorder<T>(node: Node<T> | null, visit: (key: T) => void): void {
  if (node === null) return;

  inorder(node.left, visit);
  visit(node.key);
  inorder(node.right, visit);
}

A comparator becomes important when an operation must choose a subtree based on two keys. Its contract should state which comparison result corresponds to each subtree and how equal keys are handled.

Common Mistakes

Key Takeaways

Practice

  1. Explain why a binary tree that lacks key constraints cannot be called a BST.
  2. A BST has n nodes and is highly unbalanced. What is the time complexity of inorder traversal, and why?
  3. Design a comparator contract for keys that may be equal. State how the contract determines the subtree for a smaller key, a larger key, and an equal key.

Sources

  1. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_4.htm — archive.nptel.ac.in. Accessed 24 September 2026.
  2. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_5.htm — archive.nptel.ac.in. Accessed 24 September 2026.
  3. https://archive.nptel.ac.in/content/storage2/courses/106106131/DAA_all-quizzes.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
  4. https://archive.nptel.ac.in/content/syllabus_pdf/106102064.pdf — archive.nptel.ac.in. Accessed 24 September 2026.
  5. https://onlinecourses.nptel.ac.in/noc26_cs109/preview — onlinecourses.nptel.ac.in. Accessed 24 September 2026.

Sources

  1. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_5.htm — archive.nptel.ac.in (Generated candidate citation)
  2. https://archive.nptel.ac.in/content/storage2/courses/106104021/lecture13/13_4.htm — archive.nptel.ac.in (Generated candidate citation)
  3. Design and Analysis of Algorithms — Assessments — NPTEL (Generated candidate citation)
  4. https://onlinecourses.nptel.ac.in/noc26_cs109/preview — onlinecourses.nptel.ac.in (Generated candidate citation)
  5. https://archive.nptel.ac.in/content/syllabus_pdf/106102064.pdf — archive.nptel.ac.in (Generated candidate citation)

Related topics