Given a pointer to the root node of the tree, write code to find if it is an Almost Complete Binary Tree or not?

A Binary Tree of depth d is Almost Complete iff:

- The tree is Complete Binary Tree (All nodes) till level (d-1).
- At level d, (i.e the last level), if a Node is present, then all the Nodes to the left of that node should also be present.

For example, the left tree below is NOT an Almost Complete Binary Tree but the right tree is an Almost Complete Binary Tree

NOT Almost Complete Almost Complete Binary Tree -------------------- --------------------------- _ A _ | _ A _ / \ | / \ B C | B C / \ / \ | / \ / \ D E F G | D E F G / \ / \ | / \ H I J K | H I

The left tree is not almost complete because in the last level, the nodes left to Node-J are missing (children of Node-E).

Continue reading »