Given a binary tree. Print the nodes in vertical and zigzag manner. <strong?vertical traversal<=”” strong=””></strong?vertical> For example, we have binary tree below: 1 / \ 2 3 / \ / \ 4 5 6 7 vertical traversal will output: 4 2 1 5 6 3 7 We can clearly see that we are printing the […]

# Tag Archives: binary tree

Given an unbalanced binary tree, write code to select k sample node at random straightforward solution would be to list all the nodes in any traversal order (BFS, DFS, etc) and find random k index from the n nodes in the list. But how this approach would behave if n is very large and k […]

Given a binary tree and two nodes. Find Least Common Ancestor (LCA) of the two nodes. For example given the tree T below. LCA(T, 5, 6) = 3, LCA(T, 4, 6) = 1, etc. 1 / \ 2 3 / / \ 4 5 6 \ / 7 8 With parent pointer If we are […]

Given a node in a binary tree. Find the rightmost cousin of the give node. Let’s start with an example. 1 / \ 2 3 / / \ 4 5 6 \ / 7 8 Rightmost cousin of 4 is 6, right most cousin of 7 is 8 and so on. The idea behind solving […]

Given two nodes in a binary tree with parent pointer. Find the min path from between two nodes. Note that root of the tree is not given Let’s start with an example as follows. 1 / \ 2 3 / / \ 4 5 6 \ / 7 8 Use parent pointer to find the […]

Given a Binary Tree T. 1. Find all paths from root to each of the leaves in T. 2. Find the longest path from root to a leaf (also called Max Depth or Height of the tree). 3. Find the path that has largest sum along the path in T. 4. Find distance (shortest) between […]

From wiki, A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all […]