Write an efficient algorithm that takes as input a pointer to the root of a bina

Question

Write an efficient algorithm that takes as input a pointer to the root of a binary tree and returns the length of the longest embedded “list” in the tree. For this problem, we define a “list” as a sequence of nodes on a path in the tree such that all nodes have either 0 or 1 child. Note that we use path in the traditional sense of being comprised of edges (parent, child), i.e. all paths descend the tree. Note further that nodes in the tree consist only of left child (LC), right child (RC), and data fields.

Explanation / Answer

Answer :

It calculates recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest path and length.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.