15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 11 of 12 in the free DSA Basics course · 6 lessons
Build a mental model of a binary tree, then use that model in small programs. Draw a tree from parent-child relationships, visit every node in different orders, calculate its size and height, and store it with linked nodes or an array.
A binary tree is a rooted tree in which each node has at most two children: a left child and a right child. A binary tree becomes a binary search tree only when extra ordering rules are added.
No prior tree knowledge is required.
Be comfortable with:
Use this binary tree throughout the lessons:
1 A
2 / \
3 B C
4 / \
5 D EA is the root. B and C are its children. D and E are children of B.
The tree provides these reference points:
A at level 0, B and C at level 1, and D and E at level 2.B is the parent of D. A is an ancestor of D.C, D, and E are leaves because they have no children.A, B, D, E, C.A, B, C, D, E.With linked nodes, each node can hold a value plus left and right references. In an array representation, C has no children while B does, so some layouts need empty positions to preserve parent-child locations.
The traversals and calculations described here do not mutate the tree.
Tree Terminology and Structure defines the relationships in a tree before you describe or manipulate one. Identify roots, parents, children, leaves, ancestors, depth, and levels.
Binary Tree Properties covers maximum capacity at a level and height. Height must use one stated convention consistently.
Tree Representation Techniques connects the logical tree to program storage. Compare flexible linked nodes with index-based array storage.
DFS Traversals uses parent-and-subtree structure to visit nodes recursively. Processing a node before, between, or after its subtrees creates preorder, inorder, or postorder.
BFS Traversal visits every node with a queue. The queue processes nodes level by level instead of descending into one subtree first.
Height and Size Calculation reuses the recursive subtree pattern from DFS Traversals. Recursive calls return values that combine into a count or height instead of a visit sequence.
Start by reading the diagram correctly. In the running tree, B is D’s parent. A is an ancestor of D. A binary tree allows at most two children and does not require every node to have two.
Properties give limits for what a tree can contain. At level l, a binary tree can have at most 2^l nodes when the root is level 0. Height requires a stated convention. This path uses edge-based height, so a single-node tree has height 0 and the example tree has height 2.
Traversal lessons cover all nodes in two ways:
A, B, D, E, C.A, enqueue B and C; visiting them before their children gives the level-order result A, B, C, D, E.Recursive calls through subtrees also calculate values. The size of a node’s tree is one for the node plus the sizes of its left and right subtrees. Height uses the larger child height. An empty subtree provides the base case.
Representation choices affect how directly these operations are expressed. Linked nodes suit trees with missing children at arbitrary positions. Arrays suit complete trees because index positions determine child locations. For a zero-based array, a node at index i has possible children at 2i + 1 and 2i + 2; missing positions may need explicit empty slots for a non-complete tree.
Draw the running example from its parent-child statements. Label the root, leaves, siblings, parents, ancestors, and descendants.
Mark each node’s level and depth. State that height is counted in edges, then verify that the tree’s height is 2.
Compare the actual number of nodes at each level with the maximum possible number for that level. Classify the tree only after applying the supplied definitions of full, complete, and perfect.
Trace preorder, inorder, and postorder on the same drawing. For one traversal, write the recursive calls down to empty subtrees and back.
Perform level-order traversal with a written queue. Record the queue after each node visit to check why C is visited before D.
Write recursive size and edge-based height functions. For each node, record the values returned by its children before computing the node’s own result.
Build the tree with linked nodes, then place it into a zero-based array layout. Notice where an empty slot is required if you want array indexes to keep the intended child relationships.