BINARY TREES

Tree Concepts

• Node Height

  • Height of a node is determined in relation to leaves.

  • To find the height from a leaf to a particular node, count the number of paths traversed.

  • The height of the root node equals the height of the entire tree.

• Depth vs Height

  • Depth counts down from the root to a node.

  • Height counts up from a leaf node to the node in question.

  • For example, in a tree, if node A is the root, its height is the tallest path from any leaf.

Generic Trees

• A generic tree has:

  • One node without a parent (the root).

  • Each node can have any number of children (zero or more).

• In contrast, a binary tree restricts nodes to:

  • Having at most two children (left and right).

Binary Trees

• A binary tree is defined by:

  • Each node having at most two children.

  • Children are labeled as left or right.

• Example structure:

  • A node can have no children, one child, or two children.

Binary Tree Nodes

• Nodes have two pointers:

  • One pointing to the left child.

  • One pointing to the right child.

• Structuring a binary tree is akin to structuring linked lists but expands it to accommodate two next pointers.

Types of Binary Trees

• Full Binary Tree

  • A binary tree where every node has either 0 or 2 children.

  • Example: Complete nodes have 2 children and leaves have none.

• Complete Binary Tree

  • All leaves are on the same level or the very next level.

  • If there is a gap in levels, bottom leaves must be filled from left to right without any spaces.

Tree Height Computation

• Maximum Height

  • If there are N nodes, maximum height approximates to N-1 in the worst-case scenario (linked list shape).

• Minimum Height

  • The minimum height is calculated in relation to the number of nodes placed optimally in the tree (logarithmic relation).

  • Formula involves logarithm: ( ext{minHeight} = ext{floor}( ext{log}_2(N)) )

Binary Search Trees (BST)

• Enforces an additional structure:

• For any node X:

  • All nodes in its left subtree have lesser values.

  • All nodes in its right subtree have greater values.

• This ordering structure allows for more efficient searching than a regular binary tree—improving search operations systematically.

Binary Search Tree Operations

• Traversal Methods

  • In-order: Left subtree -> Current node -> Right subtree (produces sorted output).

  • Pre-order: Current node -> Left subtree -> Right subtree.

  • Post-order: Left subtree -> Right subtree -> Current node.

• Search Operation

  • Efficiently finds nodes based on the BST properties.

• Insertion/Deletion

  • New nodes are added while maintaining the BST properties.

Conclusion

• Understanding the structure and properties of trees, especially binary trees and binary search trees, facilitates better data management and efficient searching algorithms.

• Note the differences between tree types and the essential operations in a binary search tree.