Binary Tree: Nodes and Structure

A binary tree consists of nodes with at most two children (left, right). The root has no parent node. A leaf has no children.

Example: Root A with left child B and right child C. B has the left child D.

Trees model hierarchies, expression trees, and search spaces. The recursive structure (node plus two subtrees) fits recursive algorithms.

Height as depth: Maximum Depth of Binary Tree [1].

Where used

Search indices, syntax trees, decision trees, heap representation (as an array), UI layout hierarchies. Binary trees are the minimal model for hierarchical data with two child pointers.

Depth

A binary tree consists of nodes with at most two ordered child positions. Left and right are structurally different even if both subtrees contain the same values. The empty subtree is usually represented by null.

The tree shape is to be separated from the key order. A general binary tree has no search invariant. Only a binary search tree arranges smaller and larger keys relative to the node.

For a finite tree with n nodes, there are exactly n - 1 parent-child edges. This property follows from the fact that, except for the root, each node has exactly one parent node.

Difficulty levels

1. Identify root, leaf, and subtree.
2. Distinguish structure and search order.
3. Justify the number of edges in a finite tree.

Pitfalls

Two child positions do not mean that every node has two children. A shared child node or cycle does not create a tree in the usual sense.