Melissa Guachun Here's another binary tree algorithm for all you binary tree enthusiasts out there! Solving this one took me a few days because I was trying to absorb a myriad of concepts and functions that are completely new to me. For that time these cool binary trees made me think they were plotting against me. But after some time I was able to see the forest from the trees.
Let's dive right into it, so LeetCode is asking us to determine if the height of a binary tree is balanced. It defines a height balanced binary tree as "a binary tree in which the left and right subtrees of every node differ in height no more than one".
Before figuring out this problem, there were still some technical terms that I was unaware of until now concerning binary trees. Let's look at the first example to get an idea of what a binary tree consists of:
In this binary tree the following is labeled:
Edge: the link between any two nodes
Node: an entity that contains a key or value and pointers to its child node
-leaf node/external nodes: the last node of each path, do not contain a link to child nodes
-internal node: a node having at least a child node
What left me puzzled was understanding what the height of a node is. This is where Googling comes handy. In basic terms, the height of a node is the number of edges from the node to the deepest leaf (i.e. the longer path from the node to the leaf node.
Here we see the height of the binary tree. The right subtree consisting of the root (3), the internal node of 21, and the external node (7) are indicated. Between these three nodes there are two edges. If we look at the external nodes of the left subtree, consisting of (9) and (15), they each have one edge. This fulfills the definition of the a height balanced binary tree because the left and right subtrees of every node differ in heigh by no more than one. In the right subtree, there are two edges, where as in the left subtree, there is only one.
With this cleared up, let's start trying to translate this into code. This solution will be solved recursively. In this case the root is the parameter of the nested recursive solution which will return a pair of values being the height of the binary tree and the boolean.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
We have to solve for an edge case, like if a root doesn't have any nodes. If so, it is considered a balanced tree, so we return the height of the tree along with the boolean value of True. Instead of comparing the left and right subtrees, we assign it tot he left and right values. This way, we can show that from the root, a tree with null branches is balanced.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
if not root: return [True, 0]
left, right = dfs(root.left), dfs(root.right)
Now we'll solve for if the right and left subtrees have edges and child nodes. To do this, we must check if the root of the subtree is balanced.
We do this by taking the left and right absolute value (abs) of the heights. We then compare it to 1 because that's the limited height of a balanced binary tree.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
if not root: return [True, 0]
left, right = dfs(root.left), dfs(root.right)
balanced = (left[0] and right[0] and
abs(left[1] - right[1]) <= 1)
balanced returns our boolean value of true or false depending on if the tree is balanced at all. This will test out trees from the root as well and return out boolean value. The balanced conditional will only be tree if the left and right subtrees and the root are balanced.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
if not root: return [True, 0]
left, right = dfs(root.left), dfs(root.right)
balanced = (left[0] and right[0] and
abs(left[1] - right[1]) <= 1)
return [balanced, 1 + max(left[1], right[1])]
return dfs(root)[0]
Now we must tackle how we are going to deliver the height of the binary tree once we determine it is balanced. After the boolean value is determined, we find the max values of the left and right subtree and add them by 1. 1 comes from the root of the tree and we are utilizing the function of max to return the highest number of the left and right subtrees. This will ultimately give us the height of the binary tree.
Finally in the outer level we return the height by returning the root as the parameter and a boolean which is displayed as an index of [0].
Conclusion:
This binary tree problem really threw me for a loop. It honestly took me a few days to start to grasp these functions and concepts. The fact that LeetCode labeled this problem as 'Easy' is a joke to me. But then I remind myself that I have no background in data types, so I have to cut myself some slack. As someone who has no formal training in data types or algorithms, I'm relieved that I made it through.
Resources:
https://www.programiz.com/dsa/trees
