Source: CS 225 Data Structures, UIUC
Tags: tree, binary tree, binary search tree, BST, full tree, complete tree, perfect tree, tree height, tree depth, root, leaf, parent, child, sibling, pre-order, in-order, post-order, traversal, NULL pointers in BST
Difficulty: Intermediate Prerequisites: Pointers and references in C++, linked data structures, recursion (CS 173 or equivalent). You should be comfortable with pointer-based node structures before starting.
Trees are the first non-linear data structure in CS 225, and they open the door to efficient searching, sorting, and hierarchical organisation. Where linked lists give you O(n) search, a balanced binary search tree gives you O(log n). Trees model naturally hierarchical data (file systems, HTML documents, organisational charts) and serve as the foundation for heaps, tries, B-trees, and many graph algorithms. If you are coming from lists and stacks, the jump to trees is the jump from one-dimensional to two-dimensional thinking about data.
A tree is a hierarchical structure of nodes connected by edges, where each node has data and links to its children. Binary trees restrict each node to at most two children. Binary search trees add an ordering property (left < node < right) that enables efficient lookup. Tree traversals (pre-order, in-order, post-order) are systematic ways to visit every node, and each produces a different ordering of the elements.
Tree
A hierarchical data structure consisting of nodes connected by edges. Each node contains data and zero or more links to child nodes. There is a single distinguished node called the root, and every other node is reachable from the root by a unique path.
In simple terms: "A tree is an upside-down family tree: one root at the top, branches going down, leaves at the bottom."
Root
The topmost node in a tree. It has no parent. Every tree has exactly one root.
Parent
A node that has one or more children. The parent is the node directly above in the hierarchy.
Child
A node directly below another node (its parent) in the hierarchy.
Sibling
Nodes that share the same parent.
Leaf
A node with no children. Leaves are the terminal nodes at the bottom of the tree.
Height (of a tree)
The length of the longest path from the root to any leaf. A single-node tree has height 0. Height measures how "deep" the tree extends and directly affects the worst-case performance of operations like search.
In simple terms: "Count the edges on the longest root-to-leaf path. That number is the height."
Depth (of a node)
The number of edges from the root to that node. The root has depth 0.
Binary tree
A tree in which each node has at most two children, typically called the left child and right child. One of the most common tree structures in computer science.
Full binary tree
A binary tree in which every node has either 0 or 2 children. No node has exactly one child.
In simple terms: "Every node either has two children or is a leaf. No half-occupied nodes."
Perfect binary tree
A binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level. A perfect binary tree of height h has 2^(h+1) − 1 nodes.
In simple terms: "Every level is completely filled. The tree looks perfectly symmetrical."
Complete binary tree
A binary tree in which every level is completely filled except possibly the last level, which is filled from left to right with no gaps. This is the shape property required by heaps.
In simple terms: "Fill each level left to right. You can only have 'missing' nodes at the far right of the bottom row."
Binary search tree (BST)
A binary tree with an ordering property: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This enables O(h) search, insert, and delete, where h is the tree's height.
In simple terms: "Left is smaller, right is bigger, at every single node."
NULL pointer (in a BST)
Represents a missing child. In a BST, a NULL pointer means the position where a value would go if it existed. The proof that the BST property holds relies on this: the left subtree contains only values less than the node, and the right subtree contains only values greater, and NULL marks the boundary.
Pre-order traversal
Visit the current node first, then recursively traverse the left subtree, then the right subtree. Order: Node, Left, Right. Useful for copying a tree or producing a prefix expression.
In-order traversal
Recursively traverse the left subtree, then visit the current node, then traverse the right subtree. Order: Left, Node, Right. For a BST, in-order traversal visits nodes in sorted (ascending) order.
In simple terms: "Go left as far as you can, visit, then go right. In a BST this gives you the values in order."
Post-order traversal
Recursively traverse the left subtree, then the right subtree, then visit the current node. Order: Left, Right, Node. Useful for deleting a tree (you delete children before the parent) or evaluating a postfix expression.
A tree with n nodes has exactly n − 1 edges
The root is the only node with no parent; every other node has exactly one parent
A leaf is a node with zero children
Depth is measured from the root downward (root = 0); height is measured from the leaves upward (tallest leaf-to-root path)
These terms carry over from CS 173 (discrete mathematics) and are used consistently throughout CS 225
Binary: each node has at most 2 children
Full: every node has 0 or 2 children (no single-child nodes)
Perfect: full, and all leaves are at the same depth. A perfect binary tree of height h has exactly 2^(h+1) − 1 nodes.
Complete: every level is filled except possibly the last, which is filled left to right. Heaps use complete binary trees to guarantee O(log n) height.
These properties are nested: every perfect tree is complete, every perfect tree is full, but a full tree is not necessarily complete, and a complete tree is not necessarily full.
For every node with value v:
Every value in the left subtree < v
Every value in the right subtree > v
This property holds recursively at every node in the tree
Search: compare the target with the current node, go left if smaller, right if larger, stop when found or when you hit NULL
Insert: follow the search path until you reach a NULL pointer, then place the new node there
Worst-case height: O(n) for a degenerate (linear) tree. Average-case height for random insertions: O(log n). Balanced BST variants (AVL, red-black) guarantee O(log n) height.
Every leaf node has two NULL child pointers
A BST with n nodes has exactly n + 1 NULL pointers
Proof sketch: each of the n nodes has 2 child pointer slots (total 2n pointers). Every node except the root is pointed to by exactly one non-NULL pointer, giving n − 1 non-NULL pointers. The rest are NULL: 2n − (n − 1) = n + 1.
Pre-order (Node, Left, Right)
Visit the node before its children
Produces a sequence useful for serialising or copying the tree
Recursive pattern: process current, recurse left, recurse right
In-order (Left, Node, Right)
Visit the node between its children
For a BST, produces values in ascending sorted order
Recursive pattern: recurse left, process current, recurse right
Post-order (Left, Right, Node)
Visit the node after its children
Useful for deletion (free children before parent) and expression evaluation
Recursive pattern: recurse left, recurse right, process current
All three traversals visit every node exactly once and run in O(n) time
Nodes in a perfect binary tree:
n = 2^(h+1) − 1, where h is the height.
For h = 0: 1 node. For h = 1: 3 nodes. For h = 2: 7 nodes. For h = 3: 15 nodes.
NULL pointers in a binary tree with n nodes:
NULL pointers = n + 1
Traversal mnemonics:
Pre-order: NLR (Node first)
In-order: LNR (Node in the middle)
Post-order: LRN (Node last)
File systems are trees: directories contain subdirectories and files, forming a hierarchy rooted at / (Unix) or C:\ (Windows). The DOM (Document Object Model) of a web page is a tree that browsers traverse to render HTML. Database indices often use B-trees (a generalisation of binary search trees) to enable fast lookups on disk. Compilers represent source code as abstract syntax trees (ASTs) and use traversals to generate machine code.
Students often confuse "full" and "complete." A full binary tree requires every node to have 0 or 2 children. A complete binary tree requires all levels to be filled except possibly the last, filled left to right. A tree can be complete without being full (e.g., the last level has a node with only a left child).
Students sometimes assume a BST is always balanced. An unbalanced BST can degenerate into a linked list with O(n) search time. Balanced variants (AVL, red-black) exist specifically to prevent this.
In-order traversal produces sorted output only for a BST, not for an arbitrary binary tree. Students sometimes apply this rule to non-BST trees and get confused.
"Height" and "depth" are sometimes mixed up. Height is a property of the tree (longest root-to-leaf path). Depth is a property of a specific node (distance from root to that node).
⚠️ Be able to identify whether a given binary tree is full, complete, perfect, or none of these.
⚠️ Given a BST, trace a search or insertion and show where the value ends up.
⚠️ Given a binary tree, produce the pre-order, in-order, and post-order traversal sequences.
⚠️ Know the formula for NULL pointers in a binary tree (n + 1) and be prepared to prove it.
⚠️ Know that in-order traversal of a BST produces sorted output.
⚠️ Be able to distinguish height from depth and calculate each for a given tree.
True or False: A perfect binary tree is always a complete binary tree.
Fill in the blank: In a BST, all values in the left subtree of a node are ______ the node's value.
True or False: Post-order traversal visits the root node first.
Fill in the blank: A binary tree with 10 nodes has ______ NULL pointers.
True or False: A complete binary tree must also be a full binary tree.
Q: Define the binary search tree property.
A: For every node with value v, all values in its left subtree are less than v, and all values in its right subtree are greater than v. This property holds recursively at every node.
Q: What is the difference between a full binary tree and a complete binary tree?
A: In a full binary tree, every node has either 0 or 2 children. In a complete binary tree, every level is filled except possibly the last, which is filled from left to right. A complete tree may have a node with only one (left) child at the bottom level, which would violate the full property.
Q: Give the pre-order, in-order, and post-order traversal of a BST containing 4 (root), 2 (left child of 4), 6 (right child of 4), 1 (left child of 2), 3 (right child of 2).
A: Pre-order: 4, 2, 1, 3, 6. In-order: 1, 2, 3, 4, 6 (sorted). Post-order: 1, 3, 2, 6, 4.
Q: Why does in-order traversal of a BST produce sorted output?
A: Because in-order visits left, then node, then right. The BST property guarantees everything on the left is smaller and everything on the right is larger, so visiting in L-N-R order processes values from smallest to largest.
Q: How many NULL pointers exist in a binary tree with 15 nodes? Show why.
A: 16. Each of the 15 nodes has 2 child pointer slots (30 total). 14 of those point to non-root nodes (every node except the root is someone's child). The remaining 30 − 14 = 16 pointers are NULL.
Q: What is the worst-case height of a BST with n nodes, and when does it occur?
A: O(n). It occurs when nodes are inserted in sorted (or reverse-sorted) order, producing a degenerate tree that looks like a linked list.
Trees build on the pointer-based node structures from linked lists; if you understand how a linked list node works, a tree node is the same idea with two (or more) pointers instead of one.
Tree traversals use recursion extensively, connecting to the stack-based call mechanism covered in the stacks and queues notes.
The BST ordering property is the basis for more advanced balanced trees (AVL trees, red-black trees) and for heap data structures (which use the complete-tree shape property), both covered later in CS 225.
tree, binary tree, binary search tree, BST, full binary tree, complete binary tree, perfect binary tree, root, leaf, parent, child, sibling, height, depth, level, edge, node, pre-order traversal, in-order traversal, post-order traversal, NLR, LNR, LRN, NULL pointer, tree property, balanced tree, degenerate tree, AVL tree, red-black tree, CS 225 UIUC, data structures, tree terminology