Expression Trees & Binary Trees: Traversals, Prefix/Postfix, Applications

TAKEAWAYS:

• Expression trees visually represent operator precedence and associativity in arithmetic/logic expressions, with leaves as operands and internal nodes as operators.
• Binary trees enforce a strict left-right child rule, enabling efficient traversal algorithms (inorder, preorder, postfix) critical for compiler design and database indexing.
• Prefix (Polish) and postfix (Reverse Polish) notations eliminate parentheses and operator precedence issues, used in calculators (e.g., HP calculators) and stack-based evaluation.
• Traversal methods (inorder/preorder/postorder) map directly to prefix/postfix expressions and enable recursive algorithms for tree processing.
• Binary search trees (BSTs) maintain sorted order via left < root < right, enabling O(log n) search/insert/delete—used in Daraz’s product catalog and eSewa’s transaction logs.
• Real-world applications include expression evaluation (e.g., Kathmandu traffic route optimization via priority queues), hierarchical data (e.g., WhatsApp message trees), and syntax parsing (e.g., Google’s search query parsing).

---

1. Expression Trees: Syntax Trees for Arithmetic/Logic Expressions

Expression trees are binary trees where:

• Leaves = operands (variables, constants).
• Internal nodes = operators (+, −, ×, /, ∧, ∨, etc.).
• Parent-child relationships reflect operator precedence and associativity.

Why Use Expression Trees?

• Eliminates ambiguity: Parentheses and precedence are implicit in the tree structure.
• Compiler design: Used in parsing and code generation (e.g., converting (a − b) × (c + d) to machine code).
• Efficient evaluation: Postorder traversal directly yields postfix notation, which can be evaluated using a stack.

Example: Building an Expression Tree

Infix expression: (a − b) × (c + d) Steps to build the tree:

1. Parse the expression left-to-right, respecting parentheses and precedence.
2. Operators become internal nodes; operands become leaves.
3. Parentheses dictate subtree grouping.

Tree structure:

        ×
       / \
      −   +
     / \ / \
    a b c d

Traversals and Notations

Key Insight:

• Prefix (Polish) notation = Preorder traversal.
• Postfix (Reverse Polish) notation = Postorder traversal.

---

---

2. Binary Trees: Structure and Properties

A binary tree is a tree where each node has at most two children:

• Left child
• Right child

Types of Binary Trees

Why BSTs?

• Efficient search/insert/delete: O(log n) average case (if balanced).
• Ordered traversal: Inorder traversal yields sorted output.
• Dynamic data: Used in real-time systems (e.g., NTC’s traffic signal optimization).

---

---

3. Traversals: Inorder, Preorder, Postorder

Traversals visit nodes in a specific order, critical for:

• Expression evaluation (postorder for postfix).
• Tree reconstruction (prefix/postfix strings).
• Serializing trees (e.g., saving to disk).

Traversal Algorithms (Recursive)

def inorder(node):
    if node:
        inorder(node.left)   # Left
        print(node.value)    # Root
        inorder(node.right)  # Right

```figure
{"type":"tree","root":{"v":"root","children":[{"v":"left","children":[{"v":"left-left"},{"v":"left-right"}]},{"v":"right","children":[{"v":"right-left"},{"v":"right-right"}]}]},"highlight":[0,1,2,3,4],"caption":"Recursive traversal order: left subtree → root → right subtree (inorder)"}

def preorder(node): if node: print(node.value) # Root preorder(node.left) # Left preorder(node.right) # Right

def postorder(node): if node: postorder(node.left) # Left postorder(node.right) # Right print(node.value) # Root

Worked Example: Traversals for (a + b) × (c − d)

Tree:

    ×
   / \
  +   −
 / \ / \
a b c d

---

---

4. Prefix and Postfix Notations

Prefix (Polish) Notation

• Format: Operator precedes operands (e.g., × − a b + c d).
• Advantages:
  • No parentheses needed.
  • Easy to parse left-to-right with a stack.
• Disadvantages:
  • Less intuitive for humans.
• Example: HP calculators use RPN (Reverse Polish, i.e., postfix).

Postfix (Reverse Polish) Notation

• Format: Operands precede operator (e.g., a b − c d + ×).
• Advantages:
  • No precedence rules (evaluated strictly left-to-right).
  • Used in compilers and calculators.
• Disadvantages:
  • Harder for humans to read/write.
• Evaluation with a Stack:
  1. Scan left-to-right.
  2. Push operands onto the stack.
  3. On operator, pop operands, apply operator, push result.

Example: Evaluate 3 4 + 2 × (postfix for (3 + 4) × 2):

1. Push 3, 4 → [3, 4]
2. + → pop 4, 3 → push 7 → [7]
3. Push 2 → [7, 2]
4. × → pop 2, 7 → push 14 → [14] Result: 14

---

---

5. Real-World Applications

1. eSewa: Transaction Processing

• Idea Used: Expression trees for validation rules.
• How:
  • eSewa’s backend validates transactions using postfix expressions for rules like: "amount > 0 AND balance ≥ amount" → amount balance ≥ ×.
  • Stack-based evaluation ensures rules are applied correctly without parsing errors.

2. Daraz: Product Search (BSTs)

• Idea Used: Binary Search Trees for sorted product catalogs.
• How:
  • Daraz’s search engine uses BSTs to index products by price/name.
  • Inorder traversal retrieves products in sorted order (e.g., "Show phones under Rs. 20,000").
  • Example: For products {15000, 25000, 10000, 30000}, a BST ensures O(log n) search time.

3. Kathmandu Traffic Optimization (Priority Queues as Trees)

• Idea Used: Heap (complete binary tree) for traffic signal prioritization.
• How:
  • NTC’s traffic management system uses min-heaps to prioritize routes based on congestion.
  • Example: If routes A, B, C have congestion scores {5, 3, 7}, the heap ensures the least congested (B) is processed first.

4. WhatsApp: Message Hierarchy (Binary Trees)

• Idea Used: Binary trees for thread organization.
• How:
  • WhatsApp groups use BST-like structures to sort messages by timestamp.
  • Inorder traversal displays messages in chronological order.

5. Google Search: Query Parsing (Expression Trees)

• Idea Used: Expression trees for complex search queries.
• How:
  • A query like "Nepal AND (hiking OR trekking)" is parsed into an expression tree:

        AND
       /   \
     Nepal  OR
           /   \
        hiking trekking
    

  • Postorder traversal generates a postfix string for evaluation.

---

---

6. Binary Trees vs. General Trees

---

---

7. Proof Techniques for Trees

Example: Proving the Number of Leaves in a Full Binary Tree

Statement: In a full binary tree with n internal nodes, the number of leaves is n + 1.

Proof by Induction:

1. Base Case (n = 0):
   • Tree has 1 leaf (root). 0 + 1 = 1 ✓
2. Inductive Step:
   • Assume true for n = k (leaves = k + 1).
   • For n = k + 1, add one internal node. This node must replace a leaf (to maintain fullness), increasing leaves by 1.
   • New leaves = (k + 1) + 1 = (k + 1) + 1 ✓

Conclusion: By induction, the statement holds for all n ≥ 0.

---

---

Exam Tip

1. Expression Trees:

   • Must-know: Convert infix to prefix/postfix and draw the tree. Always show traversal outputs.
   • Common pitfall: Forgetting operator precedence (e.g., × before +). Fix: Build the tree step-by-step.
   • Exam question: Given (a − b) × (c + d), write prefix/postfix and traversals. Do this in 3 minutes:
     • Prefix: × − a b + c d
     • Postfix: a b − c d + ×
     • Inorder: (a − b) × (c + d)

2. Binary Trees:

   • BST property: Always verify left < root < right in traversals.
   • Traversal order: Memorize the LRR (inorder), RLR (preorder), LRL (postorder) mnemonic.
   • Real-world link: Relate BSTs to sorted data (e.g., Daraz products, eSewa transactions).

3. Prefix/Postfix:

   • Stack evaluation: Practice converting postfix to infix and vice versa.
   • Example: Given 3 4 + 2 ×, write the infix expression ((3 + 4) × 2).

4. Diagrams:

   • Draw trees: Label nodes clearly (e.g., ×, a, b).
   • Highlight traversals: Use arrows to show left/root/right paths.

5. Applications:

   • Link to Nepal: eSewa (validation), Daraz (search), NTC (traffic).
   • Link to global: Google (query parsing), WhatsApp (threads), calculators (RPN).

---

Final Checklist for Full Marks: ✅ Correct tree structure (no orphaned nodes). ✅ All traversals (inorder/preorder/postorder) for expression trees. ✅ Prefix/postfix notations matched to traversals. ✅ BST property verified in examples. ✅ Real-world tie-ins (eSewa, Daraz, etc.). ✅ Clear diagrams with labels.