Lesson 1 · Non-linear structures

Trees, Traversals, and Binary Search Trees

Trees model hierarchy. Their recursive shape lets a solution define a contract for one subtree, then combine child results at the parent.

A hierarchy rather than a sequence

A tree stores relationships in levels instead of placing every item in one linear run. One root begins the structure, and every reachable node belongs to exactly one parent edge except that root.

The shape is useful when the data itself is hierarchical: directories contain entries, document elements contain nested elements, and expression nodes contain smaller expressions. A subtree can therefore be processed as a smaller instance of the same problem.

A connected tree contains no cycle
There is one unique path between any two nodes
Every non-root node has exactly one parent

Names for positions in a tree

A parent is one edge above a child. Nodes with the same parent are siblings. A leaf has no children, while an internal node has at least one child.

An ancestor lies on the path from the root to a node; a descendant lies below it. The node together with all descendants forms a subtree, which is the unit most recursive algorithms receive.

Root: no parent
Leaf: degree zero
Sibling: same immediate parent
Subtree: node plus every descendant

Key reference

Terms, operations, and practical uses

Tree terminology

RootThe only node with no parent.
Parent and childTwo nodes connected by one downward edge.
SiblingNodes that have the same parent.
LeafA node with no children.
SubtreeA node together with every descendant reachable below it.

Measurements and properties

DepthThe number of edges from the root to a node.
HeightThe longest downward edge count from a node to any leaf.
DegreeThe number of children attached to a node.
N − 1 edgesA connected tree with N nodes has exactly N − 1 edges and one unique path between any pair.

Tree families and uses

Binary treeEach node has at most a left child and a right child.
Binary search treeEvery subtree obeys an ordering rule, allowing one branch to be discarded during lookup.
Balanced treeKeeps height proportional to log N so search, insertion, and removal do not degrade into a chain.
Hierarchical dataFile directories, document trees, organization charts, and syntax trees naturally use parent–child structure.

Code example

Read a binary search tree in sorted order

def inorder(node, answer):
    if node is None:
        return
    inorder(node.left, answer)
    answer.append(node.value)
    inorder(node.right, answer)


class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

root = Node(8, Node(3, Node(1), Node(6)), Node(10))
result = []
inorder(root, result)
print(*result)

void inorder(TreeNode* node, vector<int>& answer) {
    if (node == nullptr) return;
    inorder(node->left, answer);
    answer.push_back(node->val);
    inorder(node->right, answer);
}

void inorder(TreeNode node, List<Integer> answer) {
    if (node == null) return;
    inorder(node.left, answer);
    answer.add(node.val);
    inorder(node.right, answer);
}

InputBST containing 8, 3, 10, 1, 6

Output1 3 6 8 10

Example

Run the example step by step

Output

Depth, height, degree, and edge count

A node's depth counts edges from the root down to that node. Its height counts the longest downward path from that node to a leaf. The tree height is therefore the height of the root.

The degree of a node is its number of children. Because every node except the root contributes one parent edge, a tree with N nodes contains exactly N − 1 edges.

Root depth is zero
A leaf has height zero when height counts edges
Wide trees use more BFS queue space
Tall trees use more DFS call-stack space

Binary, full, complete, and balanced trees

A binary tree permits at most two child positions, conventionally called left and right. A full binary tree gives each internal node exactly two children. A complete binary tree fills every level except possibly the last, which fills from left to right.

A balanced tree prevents one side from becoming much taller than the other. Balance is a performance property, not an ordering property: a balanced binary tree is not automatically a binary search tree.

Binary describes the number of child positions
Complete describes level filling
Balanced describes height control
BST describes key ordering

Depth-first traversal, one event at a time

DFS produces three useful processing moments. Preorder records the node before either subtree. Inorder records it after the left subtree and before the right. Postorder records it only after both subtrees are complete.

The recursive contract should say exactly what one call does. For inorder traversal: process the entire left subtree, record this node once, then process the entire right subtree. The animated example below exposes every descent, base case, visit, and return instead of combining several events.

Preorder: node, left, right
Inorder: left, node, right
Postorder: left, right, node
A null child is a real base-case event

Breadth-first traversal by level

Level-order traversal uses a queue. The root enters first; removing one node schedules its children at the rear, so all nodes at depth d are processed before depth d + 1.

Capture the queue length before processing a level when the output must stay grouped by depth. The queue can grow to the tree's maximum width, which is different from DFS space that follows height.

Enqueue when discovered
Dequeue in discovery order
One saved queue length separates levels

Binary search trees and valid placement

For every BST node, all keys in its left subtree must satisfy the lower side of the ordering rule, and all keys in its right subtree must satisfy the upper side. In the illustrated tree, 6 belongs to the right of 3 but still to the left of 8; its screen position must show both facts.

Search follows one branch after each comparison and costs O(h) for height h. A sorted insertion order can create height N; AVL and red-black trees use rotations and balance rules to keep height logarithmic.

Validate with bounds inherited from every ancestor
Choose and document the duplicate-key policy
Balanced search, insertion, and deletion are O(log N)

Operations and practical applications

Common operations are create, search, insert, remove, and traverse. Their cost depends on the tree family: an unordered tree may require a full traversal, while a balanced BST discards one ordered subtree per comparison.

Trees model file systems, HTML and XML documents, compiler syntax, database indexes, autocomplete dictionaries, priority queues, routing decisions, and game choices. The useful structure comes from the relationship being represented—not from drawing nodes in a triangular shape.

File and document hierarchy
Ordered indexes
Expression and syntax trees
Decision and game trees