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.


  • 0
    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
    R

    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]
    

Log in to reply
 

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