DSA and Algos Page 4: Traversals

Tree Traversals

• In-order traversal follows the sequence: Left -> Root -> Right, producing the output: 2, 7, 5, 6, 11, 1, 9, 5, 9.
• Pre-order traversal follows the sequence: Root -> Left -> Right, resulting in: 1, 7, 2, 6, 5, 11, 9, 9, 5.
• Post-order traversal follows the sequence: Left -> Right -> Root, yielding: 2, 5, 11, 6, 7, 5, 9, 9, 1.

Binary Search Trees (BST)

• An in-order traversal of a BST displays all elements in sorted order.
• Validate whether a binary tree is a BST, as this concept is commonly encountered in problem-solving.
• Time complexity for BST operations such as Accessing, Searching, Inserting, and Removing is O(log n).
• Space complexity for balanced tree traversal is O(h); for skewed trees, it is O(n).

Important Concepts

• Familiarity with pre-order, in-order, and post-order traversals is crucial, especially implemented recursively and iteratively.
• Edge cases include Empty Trees, Single Nodes, Two Nodes, and highly skewed trees resembling linked lists.

Common Routines in Trees

• Operations include Inserting and Deleting values, Counting nodes, Checking for values, and Calculating height.
• BST-specific tasks involve determining if a structure is a BST and retrieving maximum/minimum values.

Techniques

• Recursion is the primary approach for tree traversals; always check for the base case (null/none nodes).
• A recursive function can often return multiple values for complex tree operations.

Essential Tree Terms

• Neighbor: Parent or child of a node.
• Ancestor: Node reachable via parent traversal.
• Descendant: Node within the subtree.
• Degree: Number of children of a node; tree degree is the max degree among nodes.
• Distance: Edges along the shortest path between nodes.
• Level/Depth: Edges from a node to the root.
• Width: Total nodes at a particular level.
• Diameter: Longest path between any two nodes, with or without passing through the root.

Binary Tree Characteristics

• Nodes in a binary tree can have up to two children.
• Complete Binary Tree: All levels filled except possibly the last, with nodes left-aligned.
• Balanced Binary Tree: Left and right subtrees differ in height by no more than one.
• Level Order Traversal: Conducted using Breadth-First Search; check for negative nodes when summing values.

Essential Questions Regarding Trees

• For Binary Trees: Determine Maximum Depth, Invert/Flip a Tree.
• For Binary Search Trees: Identify Lowest Common Ancestor.

Suggested Problems

• For Binary Trees: explorations include Same Tree, Maximum Path Sum, Level Order Traversal, and more.
• For Binary Search Trees: tasks like Validate BST and Kth Smallest Element are critical to practice.

Graph Theory Overview

• A graph consists of nodes and vertices, with possible edges between them; edges can be directed or undirected.
• Trees are a subset of undirected graphs with unique edges connecting vertices, ensuring no cycles exist.

Learning Resources

• Videos and readings on tree structures including UC San Diego resources.
• Recommended readings on graph representation and traversal methods (DFS, BFS).
• Additional readings cover practical algorithms such as Dijkstra’s shortest path.