Return the next leaf node in tree


  • 5
    O

    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.


  • 1
    E

    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"?


  • 0
    N

    0_1505598128418_NAryTree.jpg

    
        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;
            nodeA.children.add(nodeB);
            nodeA.children.add(nodeC);
    
            nodeD.parent = nodeB;
            nodeE.parent = nodeB;
            nodeF.parent = nodeB;
            nodeB.children.add(nodeD);
            nodeB.children.add(nodeE);
            nodeB.children.add(nodeF);
    
            nodeD.parent = nodeC;
            nodeC.children.add(nodeD);
    
            nodeG.parent = nodeD;
            nodeH.parent = nodeD;
            nodeI.parent = nodeD;
            nodeD.children.add(nodeG);
            nodeD.children.add(nodeH);
            nodeD.children.add(nodeI);
    
            nodeK.parent = nodeE;
            nodeL.parent = nodeE;
            nodeM.parent = nodeE;
            nodeE.children.add(nodeK);
            nodeE.children.add(nodeL);
            nodeE.children.add(nodeM);
    
            nodeN.parent = nodeF;
            nodeO.parent = nodeF;
            nodeF.children.add(nodeN);
            nodeF.children.add(nodeO);
    
            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);
        }
    }
    

  • 0
    S
    This post is deleted!

  • 0
    M

    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;
            }
        }
        // node is not found
        else {
            for (int i=0; i<root->children.size(); i++) {
                if (nextLeafNode(root->children[i], node, ans, found_node))
                    return true;
            }
        }
        return false;
    }
    

  • 0
    D

    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]
    

  • 0
    P

    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.


  • 0
    N

    @pulkit2 said in Return the next leaf node in tree:

    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.


  • 0
    S

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


Log in to reply
 

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