Algorithm: Tree Related Problems

We already explored several problem relating to Trees, in this article I would introduce more typical tree problems

Find the lowest common ancestor

Given two nodes and the tree root, find the lowest common ancestor of two nodes

public class LowestCommonAncestor {
    public static Node findLowestCommonAncestor(Node root, Node a, Node b) {
        Info info = process(root, a, b);
        
        return info.lca;
    }
    
    private static process(Node root, Node a, Node b) {
        if (root == null) {
            return new Info(false, false, null);
        }
        
        Info leftInfo = process(root.left, a, b);
        Info rightInfo = process(root.right, a, b);
        
        boolean hasA = leftInfo.hasA || rightInfo.hasA || root == a;
        boolean hasB = leftInfo.hasB || rightInfo.hasB || root == b;
        Node lca = leftInfo.lca != null ? leftInfo.lca : rightInfo.lca;
        
        if (lca == null) {
            if ((root == a && hasB) || (root == b && hasA) || (hasA && hasB))
           		lca = root;
            }
        }
       
        return new Info(hasA, hasB, lca);
    }
}

public class Info {
    boolean hasA;
    boolean hasB;
    Node lca;
    
    public Info(boolean a, boolean b, Node lca) {
        this.hasA = a;
        this.hasB = b;
        this.lca = lca;
    }
}

Complete Binary Tree Verify

what is Complete Binary Tree?

A complete tree is a special type of binary tree where all the levels of tree are filled completely except the lowest level nodes, which are filled from as left as possible.

solution 1: level traversal

leverage tree’s level traversal algorithm, if find any leaf node, then expect all nodes after it don’t have any child nodes.

public class CompleteBinaryTreeVerify {
    public static boolean isCBT(Node root) {
        Queue<Node> queue = new LinkedList<>();
        boolean hadLeave = false;
        
        queue.add(root);
        while(!queue.isEmpty()) {
            root = queue.poll();
            
            if (root.left != null || root.right != null) {
                if (hadLeave) {
                    return false;
                } else {
                    if (root.left != null && root.right != null) {
                        queue.add(root.left);
                        queue.add(root.right);
                    } else if(root.left != null) {
                        queue.add(root.left);
                        hadLeave = true;
                    } else {
                        return false;
                    }
                }
            } else {
                hadLeave = true;
            }
        }
        return true;
    }
}

solution 2: post order traversal

public class CBTVerify {
    public boolean isCompleteTree(TreeNode root) {
        Info info = process(root);
        return info.isCBT;
    }

    private Info process(TreeNode root) {
        if(root == null) {
            return new Info(true, true, 0);
        }

        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        if (!leftInfo.isCBT || !rightInfo.isCBT) {
            return new Info(false, false, 0);
        }

        boolean isCBT = false;
        boolean isFull = false;
        int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;

        if (leftInfo.isFull) {
            if (!rightInfo.isFull) {
                isCBT = rightInfo.depth == leftInfo.depth;
                isFull = false;
            } else {
                isCBT = rightInfo.depth == leftInfo.depth || leftInfo.depth - rightInfo.depth == 1;
                isFull = rightInfo.depth == leftInfo.depth;
            }
        } else {
            isCBT = rightInfo.isFull && leftInfo.depth - rightInfo.depth == 1;
            isFull = false;
        }
        
        return new Info(isCBT, isFull, depth);
    }

    private class Info {
        boolean isFull;
        boolean isCBT;
        int depth;
        
        public Info(boolean cbt, boolean full, int dep) {
            isCBT = cbt;
            isFull = full;
            depth = dep;
        }
    }
}

Verify is the given tree is a full binary tree

What is the difference between Complete Binary Tree and Full Binary Tree?

A full binary tree is a binary tree in which all of the nodes have either 0 or 2 child. in other word, a full binary tree is a binary tree in which all nodes, except the left nodes, have two child.

A complete binary tree, all of its levels, except the last level ,have the maximum number of possible nodes. and all nodes in the last level appear as far left as possible.

public class FullTreeVerify {
	public static boolean isFullTree(TreeNode root) {
        return process(root);
    }
    
    private static boolean process(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if (root.left != null != root.right != null) {
            return false;
        }
        
        boolean leftRes = process(root.left);
        boolean rightRes = process(root.right);
        
        return leftRes && rightRes;
    }
}