# Return the next leaf node in tree

• Got this one during phone interview and choked on the backtracking:

Given a tree, if query a leaf node, return the next leaf node. If the queried node is an internal node, return whatever you want. You can define the node structure. (Not a binary tree)

Example:

``````            a
z        x
w  z  y      o   b
``````

If I query 'z' return 'y'. If I query 'y', return 'o'. If I query 'b', return null.

• a bit intimidating at first but its fairly straightforward. follow parent pointer while current node is the last child of parent. if parent becomes nil, return nil. otherwise go down next child's first child until you hit a leaf node.

are you sure the interviewer said if queried node is internal node, "return whatever you want"?

• ``````
private static class Node{
String data;
Node parent;
List<Node> children;
Node(String data){
this.data = data;
this.parent = null;
this.children = new ArrayList<Node>();
}
}

public Node getNextLeaf(Node node){
if(node == null){
return null;
}
//handling the internal node case.
if(node.children!=null && node.children.size() != 0){
//return the first leaf node.
Node result = null;
while (node!=null){
result = node;
if(node.children.size()>0) {
for (Node child : node.children) {
if (child != null) {
node = child;
break;
}
}
}else{
return result;
}
}
return result;
}else{
//handle the case of leaf nodes !
Node parent = node.parent;
while (parent!=null){
Node next = getNextChild(parent,node);
if(next!=null){
Node result = null;
while (next!=null){
result = next;
if(next.children.size()>0) {
for (Node child : next.children) {
if (child != null) {
next = child;
break;
}
}
}else{
return result;
}
}
//internal node.
return result;
}else{
//if it was the last leaf node in this subtree.
node = parent;
parent = parent.parent;
}
}
}
return null;
}

public Node getNextChild(Node parent,Node currentChild){
Node next = null;
int index = parent.children.indexOf(currentChild);
if(index == parent.children.size()-1){
return null;
}else{
//index less than parent.children.size()-1;
next = parent.children.get(index+1);
}
return next;
}

public static void main(String args[]){
FindNextLeaf findNextLeaf = new FindNextLeaf();
//findNextLeaf.getNextLeaf();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
Node nodeG = new Node("G");
Node nodeH = new Node("H");
Node nodeI = new Node("I");
Node nodeK = new Node("K");
Node nodeL = new Node("L");
Node nodeM = new Node("M");
Node nodeN = new Node("N");
Node nodeO = new Node("O");

nodeB.parent = nodeA;
nodeC.parent = nodeA;

nodeD.parent = nodeB;
nodeE.parent = nodeB;
nodeF.parent = nodeB;

nodeD.parent = nodeC;

nodeG.parent = nodeD;
nodeH.parent = nodeD;
nodeI.parent = nodeD;

nodeK.parent = nodeE;
nodeL.parent = nodeE;
nodeM.parent = nodeE;

nodeN.parent = nodeF;
nodeO.parent = nodeF;

FindNextLeaf lObj = new FindNextLeaf();
System.out.println(lObj.getNextLeaf(nodeD).data);
System.out.println(lObj.getNextLeaf(nodeK).data);
System.out.println(lObj.getNextLeaf(nodeM).data);
}
}
``````

• This post is deleted!

• A simple DFS should be able to solve this question. Here is the solution to a modified version, where if the query node is an internal node, return its leftest leaf.

``````struct Tree {
int val;
std::vector<Tree *> children;
Tree(int x): val(x) {}
};

bool nextLeafNode(Tree *root, Tree *node, Tree **ans, bool &found_node) {
// if root == null, just return false
if (!root)
return false;
// the node has been found previously, just need to find a leaf now
if (found_node) {
while (!root->children.empty())
root = root->children[0];
*ans = root;
return true;
}
// node is found
if (root->val == node->val) {
found_node = true;
// node is an internal node, find the lefest leaf
if (!root->children.empty()) {
while (!root->children.empty())
root = root->children[0];
*ans = root;
return true;
}
// node is a leaf it self, find the next leaf
else {
return false;
}
}
else {
for (int i=0; i<root->children.size(); i++) {
if (nextLeafNode(root->children[i], node, ans, found_node))
return true;
}
}
return false;
}
``````

• At each node traversed via dfs, maintain some state to indicate whether the query was found. If found, then result is the next leaf node that is encountered while `found = True`

``````def get_next_leaf(node, query):

def is_leaf(node):
for child in node.children:
if child is not None:
return False
return True

found = [False]
result = [None]
def helper(node):
# If result was found, terminate recursion early.
if node is None or res[0] is not None:
return

if is_leaf(node) and found[0]:
res[0] = node
return

if node.val == query:
found[0] = True
# If not leaf, return internal node itself.
if not is_leaf(node):
res[0] = node

for child in node.children:
helper(child)

helper(root)
return res[0]
``````

• We can do an in-order traversal and store the mapping between leaves in a hash in the pre-processing step. Now for the query we can just do a lookup in the hash.

• store the mapping between leaves in a hash

This will require extra space. Given that they have given parent pointers, extra space solution, would not meet the hiring bar.

• Form a linked list of leaf nodes. And then traverse the linked list from the given node to get the next leaf node.

• @nilesh13 There's a trade-off here though, right? Pre-processing the tree results in constant O(1) lookups and requires extra O(log N) space. On the other hand, performing the lookup each time requires no space but results in O(log N) for each lookup

• Why not level order traversal by keeping tracking level.

If you found query node save the level at get the next immediate child in the same level

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.