Find nodes in a binary tree which are at a distance K from a given node

You are given a binary tree and a node in the tree, your task is to find all the nodes in the binary tree which are at a distance K from that node. These nodes can be downwards [descendants of the node] or upwards.

For example: In this image

http://www.cs.mcgill.ca/~jeromew/comp252/images/Binary_tree.png

The nodes that are at a distance 2 from 7 are 5 (6’s left child), 11, 5 (2’s right child).

This is a coding question.

Function prototype:

void PrintKDistanceNode(Node *root, Node *node, int K)

{

}

Advertisements

Find the height of the tree

You are given an array of length N. The array stores information about an n-ary tree. And the n-ary tree has N-nodes numbered 0 – (N-1).The ith index in the array contains the parent nodes number j. Given this array find the height of the tree. The parent of the root is -1

It would be good to solve this problem in O(n).

Find the Common Ancestor

How do you find the nearest/least common ancestor of two nodes in a
1. Binary Search Tree
2. Binary Tree

Assume the following two situations in the above cases :
1. Parent pointer is given
2. Parent pointer is not given.