Tree Data Structures

Trees Overview

• Trees are non-linear and hierarchical data structures.
• Similarities to botanical trees:
  • Root: Topmost node in the tree.
  • Branches: Connections between nodes.
  • Leaves: Nodes with no children, located at the bottom of the tree.
• Hierarchical representation: The root is at the top, leaves at the bottom, which helps in representing hierarchical relationships.

Key Properties of Trees

• Root: The topmost node of the tree.
• Children: Elements directly under a node.
• Parent: Element directly above a node.
• Leaves: Elements with no children.

Tree Components and Concepts

• Nodes: Include root, parent, child, and leaf nodes.
• Edges: Connection between nodes; can be a left or right child.
• Height: The length of the longest path from the root to a leaf (e.g., for a tree of height 2, there are 3 levels: 0, 1, 2).

Binary Trees

• Definition: A binary tree has at most two children for each node.
• Visual representations show that binary trees can have different structures while containing the same nodes.

Binary Tree Classifications

• Full Binary Tree:

  • A binary tree where every node has either 0 or 2 children.
  • Example: A tree of height $h$ where all leaves are at level $h$.

• Complete Binary Tree:

  • Every level is completely filled, except possibly the last, which is filled from left to right.
  • Nodes at level $h-1$ and above have two children each.

Properties of Binary Trees

• Maximum number of nodes at level $L$ is given by: 2^L.
  • Examples:
  • Level 0: Max nodes = 2^0 = 1
  • Level 1: Max nodes = 2^1 = 2
  • Level 2: Max nodes = 2^2 = 4
• Maximum number of nodes in a binary tree of height $h$ is: 2^{h+1} - 1.

Balanced Binary Trees

• A binary tree is balanced if the height difference of the left and right subtrees of any node is at most 1.
• Properties:
  • All full binary trees are complete.
  • All complete binary trees are balanced.

Summary of Terminology

• General Tree: A set of nodes with a root and general subtrees.
• Parent and Child Nodes: Relationships between nodes.
• Leaf: A node without children.
• Siblings: Nodes sharing a parent.
• Ancestor and Descendant: Relationship on the path from root to leaf.
• Subtree: A tree consisting of a node and its children.
• Height: The number of edges in the longest path from root to leaf.

Tree Representation Methods

1. Array Based:

   • A binary tree is stored in an array where:
     • For any node at index $i$:
     • Left child is at index 2*i+1
     • Right child is at index 2*i+2
     • Parent is at index (i-1)/2
   • Pros: Memory efficient and simple implementation.
   • Cons: Not efficient for trees that are not complete, with limitations on insertion, deletion, and traversal.

2. Class Based:

   • Nodes are defined as objects, typically with attributes for value, left child, and right child.

Tree Traversal Methods

• Preorder Traversal:

  • Visit Root, Left, Right recursively.
  • Implementation illustrates recursion through visits to the current node followed by left and right subtrees.

• Inorder Traversal:

  • Visit Left, Root, Right recursively.
  • Implementation details on recursively visiting left subtree, current node, and right subtree.

• Postorder Traversal:

  • Visit Left, Right, Root recursively.
  • Focus on visiting child nodes before the current node.

Exercise

• Determine the preorder, inorder, and postorder traversal results for the binary tree with nodes: a, b, c, d, e, f, g.