Service Now Interview Question
Country: United States
Interview Type: In-Person
Something in these lines. But it gives me an incorrect output
var allNodes =[];
function NodeClass(value){
this.value = value;
}
var root = new NodeClass(20);
root.left = new NodeClass(8);
root.right = new NodeClass(22);
root.left.left = new NodeClass(4);
root.left.right = new NodeClass(12);
root.left.right.left = new NodeClass(10);
root.left.right.right = new NodeClass(14);
var target = root.left.right;
function printkdistanceNodeDown(root, k) {
// Base Case
if (root == null || k < 0) return;
// If we reach a k distant node, print it
if (k==0)
{
// console.log(root.value);
allNodes.push(root.value)
return;
}
// Recur for left and right subtrees
printkdistanceNodeDown(root.left, k-1);
printkdistanceNodeDown(root.right, k-1);
}
function printkdistanceNode(root, target , k) {
// Base Case 1: If tree is empty, return -1
if (root == null) return -1;
if (root == target)
{
printkdistanceNodeDown(root, k);
return 0;
}
// Recur for left subtree
var dl = printkdistanceNode(root.left, target, k);
// Check if target node was found in left subtree
if (dl != -1)
{
if (dl + 1 == k){
console.log(root.value);
allNodes.push(root.value);
}
else
printkdistanceNodeDown(root.right, k-dl-2);
return 1 + dl;
}
var dr = printkdistanceNode(root.right, target, k);
if (dr != -1)
{
if (dr + 1 == k){
console.log(root.value);
allNodes.push(root.value);
}
else
printkdistanceNodeDown(root.left, k-dr-2);
return 1 + dr;
}
return -1;
}
console.log(printkdistanceNode(root, target, 2));
sorry, it is not java script (it is c#), but the idea is in code, you can translate it into java script.
In function I don't use parameter "rootNode". It is because my class "BSTNode" contains reference to parent node.
If it is not allowed, then to obtain parent node just create method with input parameters "rootNode" and "currentNode", and then it will be necessary to change only 1 line in below code as follows:
foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), GetParent( rootNode, node ) } ) {
using System.Collections.Generic;
namespace BST {
public static class NodesFinder<T> {
public static BSTNode<T>[] FindNodes( BSTNode<T> rootNode, BSTNode<T> initNode, int distance ) {
var listOfStartNodes = new List<BSTNode<T>> { initNode };
var excList = new List<BSTNode<T>>();
for ( int i = 0; i < distance; i++ ) {
var inclList = new List<BSTNode<T>>();
foreach ( var node in listOfStartNodes ) {
excList.Add( node );
var nearestNodes = new List<BSTNode<T>>();
foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), node.GetParent() } ) {
if ( item == null || excList.Contains( item ) ) { continue; }
nearestNodes.Add( item );
}
inclList.AddRange( nearestNodes );
}
listOfStartNodes = inclList;
}
return listOfStartNodes.ToArray();
}
}
}
By the definition "Printing all nodes at distance k from a given node" is the general for any graph, we can use a modified version of BFS where we keep track of the level as we goes. For particular, we insert -1 (or null as a indicator) when a complete level is push onto the queue. In the case of BST we only have a maximum of two node for the first level and maximum of 4 nodes for the second level (assumption that we start from root). Otherwise if we start from any node, we just need to remember to add parent, left and right as we expand the search tree, when we reach the desire level we can stop.
Just do a BFS with tracking depth as we goes along. Store the node to return if the depth is at desired k-th level. As soon as we start processing k+1-th, we can just stop as we has seen all the k-th level node. We can modified the queue to hold the Node and the depth and pushing start node as
(node, 0)
. When ever you pop and node and pushing it child we push
(node, parent.depth + 1)
can you please explain the distance ? thank you
- Scott November 24, 2015