Facebook Interview Question SDE1s
Country: United States
If u have a parent pointer it's really simple, from a node go up, left and right (put those nodes into a queue as pairs of current: enqueued((self, self.left)), ...
Then if u dequeue only visit those that are not equal to the first element taken from the queue (don't go back where I came from).
Then the first leave encountered is it...
If u have no parent pointer, u create first a parent-pointer list, from the root to the node u start from, all other parent pointers are not needed.
Code follows...
the idea is to do a special kind of BFS:
1) I assume I have a parent pointer for each node, if I don't I can
easily get a dictionary with necessary parent pointers, which is
derived from the path from the tree root to the node given
(I need the root then, that defines the tree I can look in)
Further I assume that if I get passed a leaf I should return the
nearest leaf and not the passed in node (leaf).
2) Instead of maintaining visited array, I can simply not go
back where I came from because there are no cycles and no
forward edges in a regular binary tree
3) I just start at a node and go to the parent, left and right
...
Sample tree
p
/ \
h q
/ \
c k
/ \ \
b e m
/
p
complete implementation using parent pointers for simplicity
in python 3:
from collections import deque
def find_nearest_leaf(node):
queue = deque()
queue.append((0, None, node))
while queue:
dist, prev, cur = queue.popleft()
if dist > 0 and cur.is_leaf():
return (cur, dist)
for adj in [cur.parent, cur.left, cur.right]:
if adj is not None and adj != prev:
queue.append((dist + 1, cur, adj))
return (None, None)
class Node:
def __init__(self, value, left=None, right=None):
self.parent = None
self.left = left
self.right = right
self.value = value
if self.right is not None:
self.right.parent = self
if self.left is not None:
self.left.parent = self
def is_leaf(self):
return self.right is None and self.left is None
node_h = Node('h', Node('c', Node('b'), Node('e')), Node('K', None, Node('m', Node('p'), None)))
Node('p', node_h, Node('q'))
print(find_nearest_leaf(node_h)) # return 2
Thanks for clarifying the problem to me, now the prototype makes perfect sense and also why there can take more than O(n).
I have came up with the following algorithm.
The distance to the closest leaf is the minimum from the next three possible values: the distance from the current node to a leaf, the distance of father of the current node to a leaf or the distance from the current node to the root and from the others root child to a leaf. This algorithm runs in O(n). Code in Python
class node:
def __init__(self, value):
self.value = value
self.left = self.right = None
def compute_distance_between_nodes(n1, n2):
if n1 == None: return None
frontier = [(n1, 0, None)]
while frontier:
current_node, distance, last = frontier.pop()
if current_node == n2:
return (distance + 1, last)
if current_node.left:
frontier.append((current_node.left, distance + 1, current_node))
if current_node.right:
frontier.append((current_node.right, distance + 1, current_node))
return None
def least_height(node):
if node == None:
return 0
else:
return min(tree_height(node.left), tree_height(node.right)) + 1
def closest_leaf(root, target):
if root == target:
return least_height(root)
found_left_side = True
a = compute_distance_between_nodes(root.left, target)
if not a:
found_left_side = False
a = compute_distance_between_nodes(root.right, target)
distance_to_root, last_node = a
distance_from_root = least_height(root.left) if found_left_side else least_height(root.right)
distance_from_last_node = least_height(last_node)
return min(least_height(target), distance_to_root + distance_from_root, distance_from_last_node + 1)
Edit: Apologies for not coding what the question states. The idea of returning a tuple with the node and the distance will work
since the problem was changed to no parent pointers, here the described approach without parent pointers
# solution without parent pointer
from collections import deque
# searches the tree from the root to the node in O(n) time
# and returns the path to the node as a dictionary (key=node, value=parent)
def find_path_to_node(root, node):
path = {}
stack = [[False, root, None]]
while stack:
visited, root, parent = stack[-1]
if visited:
stack.pop()
del path[root]
else:
stack[-1][0] = True
path[root] = parent
if root == node:
break # found node
for child in [root.left, root.right]:
if child is not None:
stack.append([False, child, root])
return path
# does the find in O(n) time
def find_nearest_leaf(root, node):
parents = find_path_to_node(root, node)
queue = deque()
queue.append((0, None, node))
while queue:
dist, prev, cur = queue.popleft()
# if is it a leaf and not the node I started at, finished
if dist > 0 and cur.is_leaf():
return dist
for adj in [parents.get(cur), cur.left, cur.right]:
if adj is not None and adj != prev:
queue.append((dist + 1, cur, adj))
class Node:
def __init__(self, value, left=None, right=None):
self.left = left
self.right = right
self.value = value
def is_leaf(self):
return self.right is None and self.left is None
node_h = Node('h', Node('c', Node('b'), Node('e')), Node('K', None, Node('m', Node('p'), None)))
root = Node('p', node_h, Node('q'))
print(find_nearest_leaf(root, node_h)) # return 2
public int closestLeaf(Node node, Node root){
//Closest leaf is the min of 1. Closest leaf in subtree rooted at given node and 2. 1 + closest leaf in parents subtree
//Find the closest leaf among given nodes children
int closestNodeChild = closestLeafChild(node);
//Find parent of this node in O(N) time
Node parent = findParent(node, root);
int closestParentChild = closestLeafChild(parent);
return Math.min(closestNodeChild, 1 + closestParentChild);
}
private Node findParent(Node node, Node root){
if(root == null || root == node) return null;
if(root.left == node || root.right == node){
return root;
}
Node left = findParent(node, root.left);
Node right = findParent(node, root.right);
if(left != null) return left;
if(right != null) return right;
return null;
}
private int closestLeafChild(Node root){
if(root == null) return 0;
return 1 + Math.min(closestLeafChild(root.left), closestLeafChild(root.right));
}
I don't understand the question. As stated the closest leaf can be computed as a variation of the height of a tree, but instead of taking the maximum possible height taking the minimum height. That algorithm takes O(n) in relation with the number of nodes (in the worst case you only visit each node once). Also doesn't match the prototype of the function, you only need one node to compute the distance to the leaf. Why the root??.
Code in python
class node:
def __init__(self, value):
self.value = value
self.left = self.right = None
def closest_leaf(node):
if node == None:
return 0
else:
return min(tree_height(node.left), tree_height(node.right)) + 1
Note: You can return a tuple with the node and the height in case you are interested on the node as the problem states.
The leaf need not be necessary a descendant of the target node.The path to nearest leaf can go through the parent of the target node also.We need to consider all such scenarios.
- koustav.adorable July 26, 2017