filmov
tv
Test If A Binary Tree Is Height Balanced ('Balanced Binary Tree' on LeetCode)
Показать описание
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program that takes the root of a binary tree as input and checks whether the tree is height-balanced.
A tree is height balanced if for each node in the tree, the difference in the height of its left and right subtrees is at most one.
Approach 1 (Get Height Of Tree Rooted At Each Node)
We can perform a traversal of the tree and at each node get the height of its left and right subtrees.
This wastes time as we will be repeating work and the traversal of nodes.
Approach 2 (Drill Down With Recursion And Respond Back Up)
We can notice that we don't need to know the heights of all of the subtrees all at once.
All we need to know is whether a subtree is height balanced or not and the height of the tree rooted at that node, not information about any of its descendants.
Our base case is that a null node (we went past the leaves in our recursion) is height balanced and has a height of -1 since it is an empty tree.
So the key is that we will drive towards our base case of the null leaf descendant and deduce and check heights on the way upwards.
Key points of interest:
1.) Is the subtree height balanced?
2.) What is the height of the tree rooted at that node?
Complexities
Time: O( n )
This is a postorder traversal (left right node) with possible early termination if any left subtree turns out unbalanced and an early result bubbles back up.
At worst we will still touch all n nodes if we have no early termination.
Space: O( h )
Our call stack (from recursion) will only go as far deep as the height of the tree, so h (the height of the tree) is our space bound for the amount of call stack frames that we will create
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 10.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program that takes the root of a binary tree as input and checks whether the tree is height-balanced.
A tree is height balanced if for each node in the tree, the difference in the height of its left and right subtrees is at most one.
Approach 1 (Get Height Of Tree Rooted At Each Node)
We can perform a traversal of the tree and at each node get the height of its left and right subtrees.
This wastes time as we will be repeating work and the traversal of nodes.
Approach 2 (Drill Down With Recursion And Respond Back Up)
We can notice that we don't need to know the heights of all of the subtrees all at once.
All we need to know is whether a subtree is height balanced or not and the height of the tree rooted at that node, not information about any of its descendants.
Our base case is that a null node (we went past the leaves in our recursion) is height balanced and has a height of -1 since it is an empty tree.
So the key is that we will drive towards our base case of the null leaf descendant and deduce and check heights on the way upwards.
Key points of interest:
1.) Is the subtree height balanced?
2.) What is the height of the tree rooted at that node?
Complexities
Time: O( n )
This is a postorder traversal (left right node) with possible early termination if any left subtree turns out unbalanced and an early result bubbles back up.
At worst we will still touch all n nodes if we have no early termination.
Space: O( h )
Our call stack (from recursion) will only go as far deep as the height of the tree, so h (the height of the tree) is our space bound for the amount of call stack frames that we will create
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 10.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
0:14:17
Test If A Binary Tree Is Height Balanced ('Balanced Binary Tree' on LeetCode)
0:13:11
Balanced Binary Tree - Leetcode 110 - Python
0:16:30
Check if a binary tree is binary search tree or not
0:07:57
Check Completeness of a Binary Tree - Leetcode 958 - Python
0:10:29
Check if Binary Tree is Binary Search Tree
0:09:39
L46. Check if a tree is a BST or BT | Validate a BST
0:04:01
Check whether a binary tree is a full binary tree or not | GeeksforGeeks
0:07:56
Binary Tree - 36: Check if Binary Tree is Foldable Tree
0:09:59
Bottom View of Binary Tree | GFG POTD 5th August 2024 | JAVA | C++
0:12:17
Test If A Binary Tree Is Symmetric ('Symmetric Tree' on Leetcode)
0:07:15
Check if a tree is bst or not
0:09:21
Check if two binary trees are identical (Algorithm/code/program)
0:06:01
Determine if a binary tree is height-balanced | GeeksforGeeks
0:07:13
Binary tree - 33: Check if Two Trees are Mirror to each other
0:09:56
Validate Binary Search Tree - Depth First Search - Leetcode 98
0:07:58
check if a given binary Tree is a SumTree or not
0:14:45
Same Tree | LeetCode 100 | Check If Two Binary Trees are Identical (Iterative & Recursive Approa...
0:15:42
Check if a binary tree is subtree of another tree | DS & Algo
0:07:40
check if a tree is subtree of another tree
0:03:55
Check whether a given binary tree is perfect or not | GeeksforGeeks
0:03:57
Check for Symmetric Binary Tree (Iterative Approach) | GeeksforGeeks
0:16:58
Binary Tree - 71: Check if given Binary Tree is BST
0:06:06
Balanced Binary Tree - Leetcode 110 - Trees (Python)
0:06:57
Binary tree -35: Check if Two Binary Trees have same Structure
Комментарии