Lessons Learned: Binary trees, recursion, error values
Question 4: Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be such that the heights of the two subtrees of any node never differ by more than one.
To preface the below explanation, a binary tree is a tree data structure in which each node has at most two child nodes, as shown above. These children are referred to as the left child and the right child.
The question has given us a clear definition of what a balanced tree is: a tree such that the heights of the two subtrees never differ by more than one. We can utilize this definition to check the heights of subtrees in our given tree to check for height differences. We utilize recursion, as we normally would do in tree questions (see my introduction to recursion), to traverse down the tree.
Below is a first pass at the solution.
As you may notice, we call checkHeight() multiple times for each node. Essentially for each node, we compute its height as many times as the number of nodes above it. We can improve this by making a slight tweak to our method: We can check whether a tree is balanced and check its height at the same time. We accomplish this by checking if a subtree is unbalanced before returning its height. If it is unbalanced, we return this the form of an error value.
For the error value, we use Integer.MIN_VALUE (We’ve defined a null TreeNode to have a height of -1, so we use a value other than -1 for the error so as to not confuse the two).
Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.
Subscribe to get full access to the newsletter. Never miss an update.