110. Balanced Binary Tree — LeetCode (Python)

I got you!

Problem:

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -104 <= Node.val <= 104

Solution:

Explanation —

We use a global variable ans, to keep track of our balanced status. It is initially set to True.

We are given that —

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Therefore, we traverse all nodes in the tree and find the heights of every node’s left and right subtrees.

If the absolute difference between them is greater than one, we can say that our binary tree is not balanced. So , we update ans to False.

Finally, we return ans.

Time and Space Complexity —

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.

Thus, if n is the number of nodes in the given binary tree,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store