Complete Study Guide: Trees Data Structure

1. What is a Tree? 🌳

Definition: In computer science, a tree is an abstract model of a hierarchical structure consisting of nodes with a parent-child relationship.

Key Characteristics

Non-linear data structure (unlike arrays and linked lists)
Hierarchical organization of data
Each node can have multiple children
One root node at the top
No cycles (unlike graphs)

Real-World Applications

Common Uses:

Organization Charts: Company hierarchy
File Systems: Folders and files
Programming Environments: Abstract syntax trees
Database Indexing: B-trees and B+ trees
Decision Making: Decision trees in AI

2. Tree Terminology 📖

Essential Terms to Master:

Root: The topmost node without a parent (e.g., node A)

Internal Node: A node with at least one child (nodes A, B, C, F)

External Node (Leaf): A node without children (nodes E, I, J, K, G, H, D)

Parent: A node that has one or more children

Child: A node that has a parent

Siblings: Nodes that share the same parent

Ancestors: Parent, grandparent, great-grandparent, etc.

Descendants: Child, grandchild, great-grandchild, etc.

Depth of a Node: Number of ancestors (distance from root)

Height of a Tree: Maximum depth of any node

Subtree: A tree consisting of a node and all its descendants

Example Tree Structure:

        A (depth 0, root)
       / \
      B   C (depth 1)
     / \   \
    E   F   G (depth 2)
       / \   \
      I   J   K (depth 3)

Height of tree = 3
Internal nodes: A, B, C, F
Leaf nodes: E, I, J, G, K
Siblings: B and C; I and J

3. Tree ADT (Abstract Data Type) 🔧

Trees use positions to abstract nodes. A position is a way to refer to a node without exposing its internal structure.

Generic Methods

Method	Description	Return Type
size()	Returns the number of nodes in the tree	integer
isEmpty()	Checks if tree is empty	boolean
iterator()	Returns an iterator over tree elements	Iterator
positions()	Returns an iterable collection of all positions	Iterable

Accessor Methods

Method	Description	Return Type
root()	Returns the root position	Position
parent(p)	Returns the parent of position p	Position
children(p)	Returns an iterable of children of p	Iterable
numChildren(p)	Returns the number of children of p	Integer

Query Methods

Method	Description	Return Type
isInternal(p)	Checks if p has at least one child	boolean
isExternal(p)	Checks if p has no children (is a leaf)	boolean
isRoot(p)	Checks if p is the root	boolean

4. Tree Traversals 🚶

A traversal is a systematic way of visiting all nodes in a tree exactly once.

Preorder Traversal (NLR - Node, Left, Right)

Algorithm:

Algorithm preOrder(v)
    visit(v)                    // Visit node first
    for each child w of v
        preOrder(w)             // Then visit children
                    

Visit Order: Root → Left subtree → Right subtree

Application: Printing structured documents, creating a copy of the tree

Postorder Traversal (LRN - Left, Right, Node)

Algorithm:

Algorithm postOrder(v)
    for each child w of v
        postOrder(w)            // Visit children first
    visit(v)                    // Then visit node
                    

Visit Order: Left subtree → Right subtree → Root

Application: Computing disk space, deleting a tree, evaluating expressions

Example:

For the tree structure:

        A
       /|\
      B C D

Preorder: A, B, C, D
Postorder: B, C, D, A

5. Binary Trees 🌲

A binary tree is a tree where each internal node has at most two children (exactly two for proper binary trees). The children are an ordered pair: left child and right child.

Properties of Binary Trees

Each node has at most 2 children
Children are ordered (left vs right matters)
Can be empty
Recursive definition: A binary tree is either:
- A tree with a single node, OR
- A tree whose root has an ordered pair of children, each of which is a binary tree

Properties of Proper Binary Trees

Important Formulas:

Let: n = number of nodes, e = external nodes, i = internal nodes, h = height

e = i + 1

Number of external nodes = internal nodes + 1

n = 2e - 1

Total nodes = 2 × external nodes - 1

h ≤ i

Height ≤ internal nodes

h ≤ (n - 1)/2

Height ≤ (total nodes - 1)/2

e ≤ 2^h

External nodes ≤ 2 to the power of height

h ≥ log₂(e)

Height ≥ log base 2 of external nodes

Binary Tree ADT

The BinaryTree ADT extends the Tree ADT with additional methods:

left(p): Returns the left child of position p
right(p): Returns the right child of position p
sibling(p): Returns the sibling of position p

These methods return null when there is no left, right, or sibling.

6. Binary Tree Traversals 🔄

Inorder Traversal (LNR - Left, Node, Right)

Algorithm:

Algorithm inOrder(v)
    if left(v) ≠ null
        inOrder(left(v))        // Visit left subtree
    visit(v)                    // Visit node
    if right(v) ≠ null
        inOrder(right(v))       // Visit right subtree
                    

Visit Order: Left subtree → Node → Right subtree

Application: Drawing a binary tree, producing sorted output from BST

Traversal Summary for Binary Trees

Traversal Type	Order	Mnemonic	When to Use
Preorder	Node → Left → Right	NLR	Copy tree, prefix expressions
Inorder	Left → Node → Right	LNR	BST sorted output, infix expressions
Postorder	Left → Right → Node	LRN	Delete tree, postfix expressions

Complete Example:

        A
       / \
      B   C

Inorder: B, A, C
Preorder: A, B, C
Postorder: B, C, A

Euler Tour Traversal

A generic traversal that visits each node three times:

On the left (L): Before processing left subtree (preorder)
From below (B): Between left and right subtrees (inorder)
On the right (R): After processing right subtree (postorder)

Euler tour includes preorder, inorder, and postorder as special cases.

7. Applications of Binary Trees 💡

1. Arithmetic Expression Trees

Structure:

Internal nodes: operators (+, -, ×, ÷)
External nodes: operands (numbers, variables)

Example: (2 × (a - 1)) + (3 × b)

Printing Expressions (Inorder):

Algorithm printExpression(v)
    if left(v) ≠ null
        print("(")
        inOrder(left(v))
    print(v.element())
    if right(v) ≠ null
        inOrder(right(v))
        print(")")
                    

Output: ((2 × (a - 1)) + (3 × b))

Evaluating Expressions (Postorder):

Algorithm evalExpr(v)
    if isExternal(v)
        return v.element()
    else
        x ← evalExpr(left(v))
        y ← evalExpr(right(v))
        ◊ ← operator stored at v
        return x ◊ y
                    

2. Decision Trees

Structure:

Internal nodes: questions with yes/no answers
External nodes: decisions/outcomes

Applications: Machine learning, game AI, diagnostic systems

8. Tree Implementation Strategies 🔨

Linked Structure for Trees

Node Structure:

Element (data)
Reference to parent node
Sequence/list of children nodes

This is the most flexible implementation for general trees.

Linked Structure for Binary Trees

Node Structure (simpler than general trees):

Element (data)
Reference to parent node
Reference to left child
Reference to right child

Array-Based Representation

Formula for node placement:

rank(root) = 0
If node is left child: rank(node) = 2 × rank(parent) + 1
If node is right child: rank(node) = 2 × rank(parent) + 2

Example Mapping:

      A (0)
     / \
    B   D
   (1) (2)
   / \   \
  E   F   J
 (3) (4) (6)

Array: [A, B, D, E, F, _, J, ...]

Index: 0, 1, 2, 3, 4, 5, 6

Disadvantage: Can waste space for non-complete trees (many null entries).
Advantage: Fast access to parent and children using arithmetic.

9. Complexity Analysis ⏱️

Linked Structure Implementation

Operation	Time Complexity	Explanation
size(), isEmpty()	O(1)	Stored as instance variable
root(), parent(), left(), right()	O(1)	Direct reference access
isInternal(), isExternal(), isRoot()	O(1)	Simple checks
iterator(), positions()	O(n)	Must visit all n nodes
replace()	O(1)	Direct update of element
children(p)	O(1)	Return reference to list

Traversal Complexity

All traversals (preorder, inorder, postorder): O(n)

Each node is visited exactly once
Work done at each node is O(1)
Total time = n × O(1) = O(n)

Space Complexity

Linked Structure: O(n) - one node object per element
Array-Based: O(2^h) - where h is height (can waste space)
Recursive Traversal: O(h) - call stack depth equals height

📌 Key Takeaways

Essential Concepts:

Trees are hierarchical: Root at top, leaves at bottom, parent-child relationships
Three main traversals: Preorder (NLR), Inorder (LNR), Postorder (LRN)
Binary trees are special: At most 2 children, ordered left and right
Height matters: Determines efficiency of many operations
Proper binary trees: e = i + 1 (external = internal + 1)
Implementation choices: Linked (flexible) vs Array (compact for complete trees)

Study Tips:

Practice drawing trees and performing traversals by hand
Memorize the formulas for proper binary trees
Understand when to use each traversal type
Know the time complexity of basic operations
Practice implementing tree operations recursively

📋 Table of Contents

1. What is a Tree? 🌳

Key Characteristics

Real-World Applications

2. Tree Terminology 📖

Essential Terms to Master:

Example Tree Structure:

3. Tree ADT (Abstract Data Type) 🔧

Generic Methods

Accessor Methods

Query Methods

4. Tree Traversals 🚶

Preorder Traversal (NLR - Node, Left, Right)

Algorithm:

Postorder Traversal (LRN - Left, Right, Node)

Algorithm:

Example:

5. Binary Trees 🌲

Properties of Binary Trees

Properties of Proper Binary Trees

Important Formulas:

Binary Tree ADT

6. Binary Tree Traversals 🔄

Inorder Traversal (LNR - Left, Node, Right)

Algorithm:

Traversal Summary for Binary Trees

Complete Example:

Euler Tour Traversal

7. Applications of Binary Trees 💡

1. Arithmetic Expression Trees

Printing Expressions (Inorder):

Evaluating Expressions (Postorder):

2. Decision Trees

8. Tree Implementation Strategies 🔨

Linked Structure for Trees

Linked Structure for Binary Trees

Array-Based Representation

Example Mapping:

9. Complexity Analysis ⏱️

Linked Structure Implementation

Traversal Complexity

Space Complexity

📌 Key Takeaways

Essential Concepts:

Study Tips: