criskgl
9/30/2019 - 6:26 PM

Find Ancestors of a node in a BT

FIND ANCESTORS OF A NODE IN A BINARY TREE

  • In the NON RECURSIVE METHOD We make a function that builds a LinkedList which will be the place where the ancestors will recursively be added backwards
  • In the RECURSIVE METHOD we add the ancestors backwards adding them to the list passed by the non recursive method.
    • To know if we need to add a node to the ancestors lists we just need to check if down to the right or left if an ancestor has been found, if so, the node is part of the ancestors.
findNodeAncestorsBT.java
content_copyfile_download
public LinkedList<Integer> findAncestors(TreeNode root, TreeNode target){
    LinkedList<Integer> ancestors = new LinkedList<>();
    findAncestorsRec(root, target, ancestors);
    return ancestors;
}

public boolean findAncestorsRec(TreeNode root, TreeNode target, LinkedList<Integer> ancestors){
    if(root == null) return false;
    //TARGET FOUND IN LEFT CHILD
    if(root.left != null){
        if(root.left.val == target.val){
            ancestors.add(root.val);
            return true;
        }
    }
    //TARGET FOUND IN RIGHT CHILD
    if(root.right != null){
        if(root.right.val == target.val){
            ancestors.add(root.val);
            return true;
        }
    }
    //Search in both side and add noce is ancestor
    boolean foundLeft = false;
    boolean foundRight = false;
    //if we either see that we found the node in our 
    //left or right childs it means current node is an ancestor
    //we add our current node to
    if(root.left != null){
        if(findAncestorsRec(root.left, target, ancestors)) foundLeft = true;
    }
    if(root.right != null){
        if(findAncestorsRec(root.right, target, ancestors)) foundRight = true;
    }
    if(foundLeft || foundRight){
        //add node as ancestor and return
        ancestors.add(root.val);
        return true;
    }
    return false;
}