Univalued Binary Tree
We want to determine if a given binary tree is uni-valued, meaning that all nodes in the tree have the same value.
Approach
Define a Recursive Function: A simple way to solve this problem is by using a recursive function that traverses the tree and checks if all the nodes have the same value.
Check Node Values: In the recursive function, check if the current node’s value is the same as its parent’s value. If not, the tree is not uni-valued.
Traverse Left and Right Subtrees: Continue to traverse the left and right subtrees of the current node, performing the same check at each level.
Base Case: If the current node is
None
, return True as there are no values to compare in this branch.Final Result: The tree is uni-valued if all recursive calls return True.
Code
|
|
Example
- Input:
root = [1,1,1,1,1,null,1]
- Output:
true
- Explanation: All nodes have the value 1, so the tree is uni-valued.
Insights
Time Complexity: The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree. This is the maximum amount of space required by the recursion stack.
Simple Recursive Solution: The solution demonstrates a simple use of recursion to traverse a binary tree and perform a comparison at each node.
- We have to visit all nodes
- It does not matter which traversal you use
- When you encounter a different value immediately return false
- Search for invariant
- Definition of the term univalued
|
|