Page 63 - Data Structures Interactive Book

7.2.2 Properties of Binary Trees

Binary trees exhibit several mathematical properties that help in analyzing their

efficiency:

• The maximum number of nodes at level is 2 . For example, at level 3, a binary tree can
have up to 8 nodes.

• The maximum number of nodes in a binary tree of height ℎis 2 ℎ+1 − 1. This formula
shows how quickly the number of nodes grows as the height increases.

• The minimum number of nodes in a binary tree of height ℎis ℎ + 1, which occurs in a

skewed tree.

These properties are important because they establish the theoretical limits of binary
tree size and efficiency. They also highlight why balanced binary trees are preferred: they

minimize height and maximize efficiency.

7.2.3 Traversal Techniques (Inorder, Preorder, Postorder)

Traversal refers to the systematic process of visiting each node in the tree. Since binary
trees are hierarchical, traversal is not as straightforward as iterating through an array. Instead,

specific strategies are used to ensure that all nodes are visited in a meaningful order.

• Inorder Traversal (Left, Root, Right): This method first visits the left subtree, then the

root, and finally the right subtree. In binary search trees, inorder traversal produces
nodes in ascending sorted order, making it extremely useful for data retrieval.

• Preorder Traversal (Root, Left, Right): This method visits the root first, then the left

subtree, and finally the right subtree. Preorder traversal is often used to create a copy

of the tree or to generate prefix expressions.
• Postorder Traversal (Left, Right, Root): This method visits the left subtree, then the

right subtree, and finally the root. Postorder traversal is useful for deleting or freeing

nodes, as it ensures children are processed before their parent.

63