Binary Trees and BST

A tree is a non-linear data structure made of nodes and edges. A binary tree is a tree in which each node has at most two children.

A binary search tree, or BST, is a special kind of binary tree that keeps values in a useful order. This order lets the program search by repeatedly choosing either the left subtree or the right subtree.

You can read this note directly without first reading the hub. The only Python ideas assumed are objects with attributes, None, comparison operators, and simple recursion. For recursion support, read Recursion and the Call Stack.

In pseudocode, <- means assignment: store the value on the right into the variable or field on the left.

What You Should Be Able to Do

By the end of this note, you should be able to:

use binary-tree vocabulary correctly;
distinguish a binary tree from a binary search tree;
check whether a tree satisfies the BST rule;
trace a search path in a BST;
insert values into a BST one by one;
explain why an unbalanced BST can be inefficient;
perform pre-order, in-order, and post-order traversals;
explain why in-order traversal of a BST gives sorted output.

Tree Vocabulary

Useful vocabulary:

Term	Meaning
root	top node of the tree
parent	node with a child
child	node below another node
leaf	node with no children
edge	connection between a parent node and a child node
subtree	a smaller tree rooted at a node
left child	child usually drawn on the left
right child	child usually drawn on the right
empty link	a missing child link, often represented by `None`

Example:

In this tree:

A is the root;
B and C are children of A;
A is the parent of B and C;
D, E, and C are leaves;
the subtree rooted at B contains B, D, and E.

Binary Tree Versus Binary Search Tree

Every binary search tree is a binary tree, but not every binary tree is a binary search tree.

Structure	Rule
binary tree	each node has at most two children
binary search tree	each node has at most two children and follows the left-smaller/right-larger ordering rule

This matters because traversal works on any binary tree, but ordered search relies on the BST rule.

A binary tree can have any arrangement of values:

        10
       /  \
     30    5

This is still a binary tree because every node has at most two children. However, it is not a BST because 30 is on the left of 10, even though 30 > 10.

Binary Search Tree Rule

A binary search tree is a binary tree with an ordering rule:

all values in the left subtree are less than or equal to the current node’s value;
all values in the right subtree are greater than the current node’s value.

This rule must be true at every node, not only at the root.

Caption: A BST search follows one comparison path; after each comparison, the subtree that cannot contain the target is ignored.

This note uses the convention that duplicate values go to the left subtree because the rule says “less than or equal to” on the left. Some exam questions may assume no duplicates. Always follow the convention given in the question.

Checking Whether a Tree Is a BST

A common beginner mistake is to check only the root and its immediate children. That is not enough. The BST rule must hold across the whole left and right subtrees.

Valid BST:

        50
       /  \
     30    70
    /  \   / \
  20   40 60  80

This is valid because:

every value in the left subtree of 50 is <= 50;
every value in the right subtree of 50 is > 50;
the same rule also holds inside the subtree rooted at 30 and the subtree rooted at 70.

Invalid BST:

At first glance, 30 is correctly placed on the left of 50. However, 60 is inside the left subtree of 50, so it must also be <= 50. Since 60 > 50, the tree is not a BST.

Caption: A BST rule must hold across whole subtrees, not only immediate children.

Beginner checklist for validating a BST:

Start at the root.
Check that every value in the left subtree is small enough.
Check that every value in the right subtree is large enough.
Repeat the same check for every subtree.
Watch for values that satisfy the immediate-parent rule but violate an ancestor rule.

Searching a BST

Search for a target value by comparing it with the current node.

If the target equals the current value, the search succeeds.
If the target is smaller, move to the left child.
If the target is larger, move to the right child.
If the search reaches None, the target is not present.

Pseudocode:

current <- root
 
WHILE current is not None
    IF target = current.data THEN
        RETURN True
    ELSE IF target < current.data THEN
        current <- current.left
    ELSE
        current <- current.right
    ENDIF
ENDWHILE
 
RETURN False

Trace for searching 40:

Current node	Comparison	Next move
50	`40 < 50`	left
30	`40 > 30`	right
40	`40 = 40`	found

Trace for searching 35 in the same tree:

Current node	Comparison	Next move
50	`35 < 50`	left
30	`35 > 30`	right
40	`35 < 40`	left
`None`	empty link reached	not found

The second trace is just as important as the first one. A failed search does not stop at the nearest value. It stops only when the next link to follow is empty.

Inserting into a BST

Insertion follows the same comparison path as search. When the correct empty link is found, the new node is attached there.

Example insertion order:

50, 30, 70, 20, 40

Result:

Insertion trace:

Value inserted	Comparisons	Position
50	tree empty	root
30	`30 < 50`	left child of 50
70	`70 > 50`	right child of 50
20	`20 < 50`, `20 < 30`	left child of 30
40	`40 < 50`, `40 > 30`	right child of 30

The same comparison rule is used for search and insertion. The difference is that search stops with found/not found, while insertion attaches a new node at the empty position.

Caption: BST insertion follows one comparison path from the root until an empty child link is found; the new node is attached at that link.

Insertion Order Matters

The values in a BST are not automatically balanced. The shape depends on insertion order.

Insertion order:

5, 12, 13, 15, 42, 50

can produce a skewed tree:

This tree still satisfies the BST rule, but it is inefficient because search behaves almost like a linked list.

A more balanced tree has shorter search paths:

        15
       /  \
     12    42
    /  \     \
   5   13     50

Caption: The same values can form either a skewed or a more balanced BST; the tree shape controls how many comparisons a search may need.

For a balanced BST, search can take about $O (lo g n)$ comparisons. For a badly skewed BST, worst-case search can take $O (n)$ comparisons. The syllabus does not require self-balancing tree algorithms, but you should understand why tree shape affects search time.

Python BST Model

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value <= root.data:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root
 
 
def search(root, target):
    current = root
    while current is not None:
        if target == current.data:
            return True
        if target < current.data:
            current = current.left
        else:
            current = current.right
    return False

This code is intentionally small. It focuses on the BST ordering rule and search path, not on advanced cases outside syllabus scope.

Tracing Recursive Insert

In the insert() function, each recursive call returns the root of the subtree after insertion. That is why the code assigns:

root.left = insert(root.left, value)

or:

root.right = insert(root.right, value)

For beginners, read this as: “insert the value into the smaller subtree, then reconnect that subtree to the current node.”

Example: inserting 25 into this tree:

Trace:

Call	Meaning	Return reconnects to
`insert(50, 25)`	`25 < 50`, insert into left subtree	`50.left`
`insert(30, 25)`	`25 < 30`, insert into left subtree	`30.left`
`insert(20, 25)`	`25 > 20`, insert into right subtree	`20.right`
`insert(None, 25)`	empty position found	new node `25`

After insertion:

The important idea is that recursion travels down the tree, creates the node at an empty link, then reconnects each subtree on the way back.

Array Implementation of a Binary Tree

A binary tree or BST may also be represented using arrays or a table. Instead of storing real memory addresses, the left and right pointers store array indices.

Example BST:

One possible table representation is:

Index	Data	Left Pointer	Right Pointer
0	15	1	2
1	12	3	5
2	50	4	`None`
3	5	`None`	`None`
4	42	`None`	`None`
5	13	`None`	6
6	14	`None`	`None`

If root = 0, the root node is stored at index 0. The Left Pointer and Right Pointer fields tell us where to go next. None means there is no child in that direction.

In exam-style table questions, do not read the array from top to bottom and assume that this is the tree order. Always follow the pointers from the root.

Tree Traversals

Traversal means visiting every node in a systematic order.

Caption: The traversal name tells when the current root is visited: pre-order visits it before subtrees, in-order between left and right, and post-order after subtrees.

For this example tree:

The traversal orders are:

Traversal	Rule	Result
pre-order	root, left, right	A, B, D, E, C
in-order	left, root, right	D, B, E, A, C
post-order	left, right, root	D, E, B, C, A

Beginner memory aid:

pre-order: process the root before its subtrees;
in-order: process the root in between left and right;
post-order: process the root after its subtrees.

Traversal pseudocode:

PreOrder(node):
    IF node is not None THEN
        VISIT node
        PreOrder(node.left)
        PreOrder(node.right)
    ENDIF
 
InOrder(node):
    IF node is not None THEN
        InOrder(node.left)
        VISIT node
        InOrder(node.right)
    ENDIF
 
PostOrder(node):
    IF node is not None THEN
        PostOrder(node.left)
        PostOrder(node.right)
        VISIT node
    ENDIF

The only difference is the position of VISIT node.

Traversal Trace Method

A good way to avoid mistakes is to ask: when should I write down the current node?

Traversal	When to write the current node
pre-order	when first reaching the node
in-order	after finishing the left subtree
post-order	after finishing both left and right subtrees

Caption: Pre-order, in-order, and post-order use the same tree and nodes; they differ only in whether the current root is written before, between, or after its subtrees.

Worked example:

        10
       /  \
      7    11
     / \     \
    6   8     20
         \   /  \
          9 14  22

Traversal	Result
pre-order	10, 7, 6, 8, 9, 11, 20, 14, 22
in-order	6, 7, 8, 9, 10, 11, 14, 20, 22
post-order	6, 9, 8, 7, 14, 22, 20, 11, 10

A traversal algorithm does not require the tree to be a BST. You can traverse any binary tree. However, sorted output is only guaranteed for in-order traversal when the tree is a BST.

In-Order Traversal of a BST

In-order traversal of a BST gives sorted output because:

the left subtree contains smaller or equal values;
the current node is visited next;
the right subtree contains larger values.

Python:

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.data] + inorder(root.right)
 
 
def preorder(root):
    if root is None:
        return []
    return [root.data] + preorder(root.left) + preorder(root.right)
 
 
def postorder(root):
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.data]

If values are inserted as 50, 30, 70, 20, 40, in-order traversal returns:

20, 30, 40, 50, 70

That sorted result depends on the BST ordering rule. If the same shape is just an ordinary binary tree with unordered values, in-order traversal will still visit every node, but it will not necessarily produce sorted output.

Search, Insert, and Traversal Compared

Task	What it does	Main trace question
search	follows one comparison path	Which child should I move to next?
insert	follows one comparison path, then attaches a node	Where is the empty link?
traversal	visits every node	When do I write down the current node?

Search and insertion usually follow only one path from the root. Traversal visits the whole tree.

Exam Trace Checklist

For BST questions, record:

the root node;
the target or value being inserted;
each comparison;
whether you move left or right;
the empty link where search fails or insertion happens;
the traversal rule if every node must be visited.

For traversal questions, do not rely on intuition. Use the exact order:

pre-order:  root, left, right
in-order:   left, root, right
post-order: left, right, root

Syllabus Boundary

Core:

binary tree concepts;
BST search and insertion;
pre-order, in-order, and post-order traversals;
in-order traversal as sorted output for a BST;
basic table or pointer representation of binary trees and BSTs.

Excluded as core:

edit and deletion of nodes from a BST;
self-balancing tree algorithms.

Deletion and self-balancing may appear as enrichment in some textbooks, but they are not needed as core algorithms here.

Common Mistakes

Assuming every binary tree is a BST.
Checking only the root rule and forgetting that the BST rule must hold at every node.
Forgetting that a value in a subtree must also obey ancestor constraints.
Reversing left and right in the search path.
Stopping a failed search too early, before reaching an empty link.
Assuming insertion order does not affect tree shape.
Visiting the root too early in in-order traversal.
Assuming in-order traversal always gives sorted output for any binary tree.
Reading an array-based tree table from top to bottom instead of following pointers.
Treating BST deletion as required core content.

Check Your Understanding

What is the maximum number of children a binary tree node can have?
Why is every BST a binary tree, but not every binary tree is a BST?
In this note’s convention, where should a duplicate value go in a BST?
What does it mean if BST search reaches None?
Which traversal gives sorted output for a BST?
Why can a skewed BST search take $O (n)$ time?
For pre-order traversal, when is the root visited?
In an array-based tree table, what do the left and right pointer fields store?

Answers:

Two.
A BST has the binary-tree shape rule plus an ordering rule. A binary tree only needs each node to have at most two children.
Into the left subtree, because this note uses <= on the left and > on the right.
The target is not present in the tree.
In-order traversal.
A skewed BST may have height close to $n$ , so search may need to follow almost every node along one path.
Before the left and right subtrees.
They store the indices of the left and right child nodes, or an empty marker such as None or -1.

Singapore H2 Computing Wiki

Start Here

Binary Trees and BST

Binary Trees and BST

What You Should Be Able to Do

Tree Vocabulary

Binary Tree Versus Binary Search Tree

Binary Search Tree Rule

Checking Whether a Tree Is a BST

Searching a BST

Inserting into a BST

Insertion Order Matters

Python BST Model

Tracing Recursive Insert

Array Implementation of a Binary Tree

Tree Traversals

Traversal Trace Method

In-Order Traversal of a BST

Search, Insert, and Traversal Compared

Exam Trace Checklist

Syllabus Boundary

Common Mistakes

Check Your Understanding

Graph View

Table of Contents

Backlinks

Singapore H2 Computing Wiki

Start Here

Binary Trees and BST

Binary Trees and BST

What You Should Be Able to Do

Tree Vocabulary

Binary Tree Versus Binary Search Tree

Binary Search Tree Rule

Checking Whether a Tree Is a BST

Searching a BST

Inserting into a BST

Insertion Order Matters

Python BST Model

Tracing Recursive Insert

Array Implementation of a Binary Tree

Tree Traversals

Traversal Trace Method

In-Order Traversal of a BST

Search, Insert, and Traversal Compared

Exam Trace Checklist

Syllabus Boundary

Common Mistakes

Check Your Understanding

Related Notes

Graph View

Table of Contents

Backlinks