Difference on Trees 1. Concept Tree difference means applying the difference-array technique to a tree structure instead of a linear array. It is almost always used together with LCA (lowest common ancestor).
On an array, prefix sum and difference are inverse operations:
prefix sum <----- inverse -----> difference On a tree, the analogue of “prefix sum” is the subtree sum: after all marks have been placed, the true value at node u equals the sum of the difference values over the whole subtree rooted at u. That aggregation is done with a single post-order DFS.
Read note →Lowest Common Ancestor (LCA) 1. Definition LCA (Lowest Common Ancestor) refers to finding, in a rooted tree, the nearest (deepest) common ancestor of two given nodes x and y.
Using the reference tree below as an example:
LCA(5, 8) = 1 LCA(6, 10) = 3 Reference Tree 1 / \ 2 3 / | \ | \ 11 4 5 6 7 | 8 / \ 9 10 2. Naive Solution Steps:
Read note →What is a Tree? Concept: A Non-Linear Hierarchical Structure Tree is an abstract data type used to simulate data with hierarchical relationships. It consists of n (n ≥ 0) finite nodes. It is a non-linear data structure, in contrast to the linear structures we studied earlier such as lists, stacks, and queues. In a tree structure, there is a special node called the Root. The remaining nodes can be divided into m (m ≥ 0) disjoint sets T₁, T₂, …, Tₘ, each of which is itself a tree, referred to as a Subtree of the root. Real-Life Examples Book table of contents: The book is the root node, chapters are intermediate nodes, and sections are leaf nodes. File system: The root directory is the root node, subdirectories at each level are intermediate nodes, and files are leaf nodes. Key Terminology (Based on the tree diagram with nodes A, B, C, D, E, F, G, H, I, K)
Read note →What is Depth-First Search? Concept: Go All the Way Down One Path Depth-First Search (DFS) is an algorithm for traversing or searching trees or graphs. Its core idea is: starting from the root node, explore each branch as deeply as possible. When exploring along a path and all children of a node have been visited, the algorithm backtracks to that node’s parent and continues exploring any unvisited children. This process is typically implemented using recursion, which naturally uses the function call stack to handle the “going deeper” and “backtracking” phases. Traversal Order The order in which DFS visits nodes is closely tied to the order of recursive calls. It always completes the full exploration of one subtree before moving on to the next sibling subtree.
Read note →