Trees and Binary trees

General Tree Terminology

• Root: The topmost node in a tree.
• Edge: The link between two nodes.
• Parent/Child: A node is a parent to the nodes it connects to below it (its children).
• Leaf: A node with no children.
• Subtree: A tree consisting of a node and all of its descendants.
• Height of a Tree: The number of edges on the longest path from the root to a leaf.
• Depth of a Node: The number of edges from the root to that node.

Binary Tree (BT)

A Binary Tree is a specific type of tree where each node can have at most two children: a left child and a right child.

Binary Tree Traversal

Traversal is the process of visiting all the nodes of a tree. The three most common depth-first traversals are:

• In-order (Left, Root, Right): Visits the left subtree, then the root, then the right subtree. For a BST, this yields the nodes in sorted order.
• Pre-order (Root, Left, Right): Visits the root, then the left subtree, then the right subtree. Useful for creating a copy of the tree.
• Post-order (Left, Right, Root): Visits the left subtree, then the right subtree, then the root. Useful for deleting nodes from the tree.

There is also Level-order Traversal (a breadth-first approach), which visits nodes level by level, from left to right. This is typically implemented using a queue.

Below is an interactive simulation that demonstrates these traversal methods on a sample tree. Click on a traversal type to see the order in which nodes are visited.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree with a special property:

For any given node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This property must hold for all nodes in the tree.

Operations:

• Search, Insertion, Deletion: O(h), where h is the height of the tree. In a balanced BST, this is O(log n). In the worst case (a skewed tree), it's O(n).

BSTs allow for fast searching, insertion, and deletion of items. However, their efficiency depends on them being "balanced". Unbalanced BSTs can degenerate into linked lists, leading to O(n) performance. Self-balancing BSTs like AVL trees or Red-Black trees (used in C++ std::map) solve this problem.