Find max distance between alive tree nodes

Q: Find max distance between alive tree nodes

This question evaluates a candidate's ability to design and analyze efficient tree algorithms and data structures, focusing on tree traversal, diameter-related reasoning, and meeting specified complexity bounds (O(n) time, O(h) space).

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a binary tree, define alive nodes. Base case: alive nodes are the leaves. Find the maximum distance (number of edges) between any two alive nodes; this is the tree diameter when alive nodes are leaves. Provide an O(n) time, O(h) space algorithm. Follow-ups: (

now each node has a boolean alive flag specified arbitrarily; compute the maximum distance whose endpoints are alive (intermediate nodes may be any). (
support online updates to a node’s alive flag and queries for the current maximum distance.

Find max distance between alive tree nodes

Overview

Comments (0)