Return the next leaf node in tree


  • 4
    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!

Log in to reply
 

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