Solution Found!
You are given a binary tree T = (V, E) (in adjacency list format), along with a
Chapter 3, Problem 3.18(choose chapter or problem)
You are given a binary tree T = (V, E) (in adjacency list format), along with a designated rootnode r V . Recall that u is said to be an ancestor of v in the rooted tree, if the path from r to vin T passes through u.You wish to preprocess the tree so that queries of the form is u an ancestor of v? can beanswered in constant time. The preprocessing itself should take linear time. How can this bedone?
Questions & Answers
QUESTION:
You are given a binary tree T = (V, E) (in adjacency list format), along with a designated rootnode r V . Recall that u is said to be an ancestor of v in the rooted tree, if the path from r to vin T passes through u.You wish to preprocess the tree so that queries of the form is u an ancestor of v? can beanswered in constant time. The preprocessing itself should take linear time. How can this bedone?
ANSWER:Step 1 of 2
Binary tree is a tree like data structure, where the data is stored as nodes in a tree. The nodes are connected through edges. Each node can have at most 2 children. That is a node can have 0, 1 or 2 children only.