Binary trees are fundamental data structures in computer science. They consist of nodes connected in a hierarchical manner, with each node having at most two children. This structure allows for efficient storage and retrieval of data.

Binary trees can be represented using linked structures or arrays. Traversing these trees is crucial for many operations. Three main traversal methods - preorder, inorder, and postorder - offer different ways to visit nodes, each with specific applications in problem-solving.

Binary Tree Representation

Representation of binary trees

Linked structure representation

• Each node contains data and references to its left and right child nodes
• Nodes dynamically allocated in memory allows for flexible tree structure
• Easily insert or delete nodes by updating references

Array representation

• Binary tree stored in an array with specific indexing rules
• For a node at index $i$, left child at $2i+1$, right child at $2i+2$
• Parent of node at index $i$ located at $\lfloor(i-1)/2\rfloor$
• Requires fixed size array and may waste space for incomplete trees (sparse arrays)

Binary Tree Traversals

Comparison of tree traversal methods

Preorder traversal (NLR: Node, Left, Right)

• Visit root node first, then recursively traverse left and right subtrees
• Useful for creating a copy of the tree or prefix expression evaluation

Inorder traversal (LNR: Left, Node, Right)

• Recursively traverse left subtree, visit root, then traverse right subtree
• Yields nodes in non-decreasing order for binary search trees (BSTs)

Postorder traversal (LRN: Left, Right, Node)

• Recursively traverse left and right subtrees, then visit root node
• Useful for deleting nodes or postfix expression evaluation

Algorithms for tree traversal

Recursive algorithms

• Use recursive function calls to traverse the tree
• Base case handles empty tree or null node
• Recursive case processes current node and calls function on left and right subtrees

Iterative algorithms

• Use stack or queue data structure to track nodes during traversal
• Preorder uses stack to simulate recursive calls (push right child first, then left)
• Inorder uses stack to keep track of visited nodes (push all left children, then backtrack)
• Postorder uses two stacks or modifies preorder traversal (push root to additional stack after processing)

Applications of tree traversals

Searching for specific value in binary search tree

• Perform inorder traversal to obtain sorted order of elements (ascending)
• Binary search can locate value efficiently in $O(\log n)$ time

Evaluating arithmetic expressions represented as binary trees

• Use postorder traversal to evaluate subexpressions and combine results
• Operators are non-leaf nodes, operands are leaf nodes (constants or variables)

Serializing and deserializing binary trees

• Use preorder or postorder traversal to convert tree to linear representation (array or string)
• Reconstruct tree from serialized data using same traversal order and marker for null nodes

Implementing binary tree algorithms

• Calculate height or depth of binary tree using postorder traversal (max depth of subtrees + 1)
• Find lowest common ancestor (LCA) of two nodes using preorder traversal and recursion
• Check if binary tree is balanced (heights of left and right subtrees differ by at most 1) or a valid BST (inorder traversal yields sorted sequence)