2773. Height of Special Binary Tree
Problem Description
You are given the root node of a special binary tree which is defined by nodes numbered from 1
to n
. Unlike a regular binary tree, this special binary tree has a unique property for its leaves. These leaves are numbered b_1
through b_k
, representing their order. Here's what makes the leaves special:
- If a leaf node
b_i
has a right child, then this right child will be the next leaf in the order,b_(i+1)
, unlessb_i
is the last leaf (i = k
), in which case its right child loops back to the first leaf,b_1
. - Conversely, if a leaf node
b_i
has a left child, that child is the previous leaf in the order,b_(i-1)
, unlessb_i
is the first leaf (i = 1
), in which case its left child is the last leaf,b_k
.
Your task is to calculate the height of this binary tree. The height is the length of the longest path from the root node to any other node in the tree.
Intuition
To find the height of the tree, we need to determine the longest path from the root node down to the farthest leaf node. The solution involves a depth-first search (DFS) algorithm to traverse the tree. The intuition behind using DFS is that we can explore as far down a branch as possible before backtracking, thus naturally finding the longest path.
With DFS, we start from the root and go as deep as possible along each branch before backtracking, which allows us to calculate the depth (d
) for each node. We keep track of the maximum depth we encounter during our traversal using a variable, ans
, that is initialized to 0. As we dive into each node, we increment the depth.
We have two important conditions to check at each node:
- For the left child of a node, we ensure that it is not coming back to the current node via the special property of right child equals parent node (
root.left.right != root
), because in that case, it would not be a valid path down the tree; it would be moving back up and shouldn't be considered for depth calculation. - The same logic applies to the right child (
root.right.left != root
).
By ensuring these conditions, we accurately calculate the depth only for paths that go down the tree. During DFS, every time we move down a level to a child node, we increase d
by 1. Finally, when the DFS is completed, ans
will hold the maximum depth valueāthat is, the height of the tree.
Solution Approach
The implementation of the solution uses a recursive depth-first search (DFS) algorithm to traverse the binary tree and find its height. The main steps of the solution are as follows:
-
Define a helper function
dfs
that takes two arguments:root
, which is the current node, andd
, which is the current depth from the root node to the current node. -
Initialize a variable
ans
in the outer scope of thedfs
function (usingnonlocal
in Python) to keep track of the maximum depth encountered during the traversal of the tree. -
In the
dfs
function, updateans
to be the maximum of its current value or the depthd
. -
Check the left child of the current node. If the current node's left child exists and its right child is not the current node itself (
root.left.right != root
), then recurse on the left child with an increased depthd + 1
. -
Check the right child of the current node. If the current node's right child exists and its left child is not the current node itself (
root.right.left != root
), then recurse on the right child with an increased depthd + 1
. -
The recursion will eventually visit all the nodes in the binary tree while respecting the special property of the leaves. Since
ans
is updated at each node with the maximum depth, by the end of the recursion, it will hold the value of the height of the tree. -
Call the
dfs
function initially with theroot
of the tree and a starting depth of0
. -
After the
dfs
function has completed the traversal, return the value ofans
, which is the height of the given binary tree.
The dfs
helper function is necessary to perform the depth-first search, and the use of the nonlocal
keyword allows us to modify the ans
variable defined outside of the function scope.
This approach ensures that all pathways down the tree are explored, and only valid pathways that follow the specific properties of this special binary tree are considered when calculating the maximum depth.
By using this recursive DFS strategy, we are able to calculate the height of the tree efficiently without having to separately store or manage the nodes visited.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Suppose we have a special binary tree with 5
nodes where 3
is the root, and the leaves are ordered as follows: 1
, 4
, and 5
. The special property indicates that leaf 1
has a right child which is leaf 4
and similarly, leaf 4
has a right child which is leaf 5
. Leaf 5
, being the last leaf, has its right child linked back to the first leaf, 1
. According to the special property, leaves shouldn't have the parent node as an immediate right or left child.
Here is our example tree for reference:
3 / \ 2 2 / \ \ 1 4 5 \ / 5 1
Now let's walk through the solution approach:
-
Define the helper function
dfs
with the root node3
and the current depthd
which is0
. -
Initialize
ans
to0
. This will keep track of the maximum depth. -
Inside
dfs
, compare the current depth (starting with0
for the root) withans
, and updateans
if the depth is greater. -
Check the left child of node
3
, which is node2
. It does not violate the special property, so we performdfs
on this node with a depth of1
(d + 1
). -
Node
2
has a left child1
. Recursedfs
with node1
. The current depth is2
. Since this is a leaf, and it doesn't have a left child linking back to its parent (3
), we updateans
to2
. -
Node
2
(left child of the root) also has a right child4
, but we don't recurse here since4
has a right child which is5
, not2
. -
Now go back to the root node
3
and check its right child, which is another node2
. Follow the same process as in steps 4 and 5. Since node2
does not have a left child, we move to its right child5
. -
We recurse on node
5
with a depth of2
. Since node5
does not have a left child that links back to its parent (2
), we check further down. We arrive at node1
, which is leaf5
's right child, but we don't recurse here because its right child loops back to the starting leaf, thus forming a cycle, not a downward path. -
After this, finish the traversal, and
ans
now holds the maximum depth we encountered, which is2
. -
We return
ans
as the final answer, so in this case, the height of the tree is2
.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.left = left
6 self.right = right
7
8class Solution:
9 def heightOfTree(self, root: Optional[TreeNode]) -> int:
10 # Helper function to perform a depth-first search to calculate the height.
11 def dfs(node: Optional[TreeNode], depth: int):
12 # Access the outer variable 'max_height' to keep track of the tree's height.
13 nonlocal max_height
14 # Update the maximum height reached so far.
15 max_height = max(max_height, depth)
16 # Recurse on the left child if it exists and is not creating a cycle.
17 if node.left and node.left.right != node:
18 dfs(node.left, depth + 1)
19 # Recurse on the right child if it exists and is not creating a cycle.
20 if node.right and node.right.left != node:
21 dfs(node.right, depth + 1)
22
23 # Initialize the maximum height to 0.
24 max_height = 0
25 # Start the DFS from the root node at depth 0.
26 dfs(root, 0)
27 # Return the maximum height of the tree.
28 return max_height
29
1class Solution {
2 private int maxDepth; // renaming 'ans' to 'maxDepth' for better clarity
3
4 // Method to find the maximum depth of a binary tree
5 public int heightOfTree(TreeNode root) {
6 // Start the depth-first search from the root with an initial depth of 0
7 dfs(root, 0);
8 // After DFS is complete, `maxDepth` will contain the height of the tree
9 return maxDepth;
10 }
11
12 // Helper method to perform a depth-first search on the tree
13 private void dfs(TreeNode node, int depth) {
14 // Update the maximum depth reached so far
15 maxDepth = Math.max(maxDepth, depth);
16
17 // Increment the depth because we're going one level deeper in the tree
18 depth++;
19
20 // Recursively call the DFS method on the left child, if it's not null
21 // and it doesn't incorrectly point back to the current node
22 if (node.left != null && node.left.right != node) {
23 dfs(node.left, depth);
24 }
25
26 // Similarly, recursively call the DFS method on the right child with the same checks
27 if (node.right != null && node.right.left != node) {
28 dfs(node.right, depth);
29 }
30 }
31}
32
33// Definition for a binary tree node.
34class TreeNode {
35 int val;
36 TreeNode left;
37 TreeNode right;
38 TreeNode() {}
39 TreeNode(int val) { this.val = val; }
40 TreeNode(int val, TreeNode left, TreeNode right) {
41 this.val = val;
42 this.left = left;
43 this.right = right;
44 }
45}
46
1#include <functional> // for std::function
2
3// Definition for a binary tree node.
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 // Function to find the height of a binary tree.
16 int heightOfTree(TreeNode* root) {
17 // Variable to store the final answer - the height of the tree.
18 int maxDepth = 0;
19
20 // Lambda function to perform a depth-first search on the tree.
21 // It captures the maxDepth by reference.
22 std::function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int depth) {
23 // Update maxDepth based on the current depth.
24 maxDepth = std::max(maxDepth, depth);
25
26 // Increment depth for the next level.
27 ++depth;
28
29 // If there's a left child and it's not pointing back to the current node (to avoid cycles),
30 // recurse into the left subtree.
31 if (node->left && node->left->right != node) {
32 dfs(node->left, depth);
33 }
34
35 // Do the same for the right child.
36 if (node->right && node->right->left != node) {
37 dfs(node->right, depth);
38 }
39 };
40
41 // Invoke the DFS starting from the root at depth 0.
42 dfs(root, 0);
43
44 // Return the maximum depth, which is the height of the tree.
45 return maxDepth;
46 }
47};
48
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 val: number
6 left: TreeNode | null
7 right: TreeNode | null
8 constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
9 this.val = (val === undefined ? 0 : val)
10 this.left = (left === undefined ? null : left)
11 this.right = (right === undefined ? null : right)
12 }
13}
14
15/**
16 * Computes the height of a binary tree.
17 * @param {TreeNode | null} root - The root node of the binary tree.
18 * @return {number} The height of the tree.
19 */
20function heightOfTree(root: TreeNode | null): number {
21 // Initialize the answer to zero
22 let maxHeight = 0;
23
24 /**
25 * Depth-first search recursive helper function to determine the height of the tree.
26 * @param {TreeNode | null} node - The current node.
27 * @param {number} depth - The current depth of the node in the tree.
28 */
29 const dfs = (node: TreeNode | null, depth: number) => {
30 if (node === null) {
31 // If the node is null, we are at the end of a path, so update the answer if necessary
32 maxHeight = Math.max(maxHeight, depth);
33 return;
34 }
35
36 // If the left child is not null and doesn't point back to the current node (to avoid cycles)
37 if (node.left !== null && node.left !== node) {
38 dfs(node.left, depth + 1);
39 }
40
41 // If the right child is not null and doesn't point back to the current node (to avoid cycles)
42 if (node.right !== null && node.right !== node) {
43 dfs(node.right, depth + 1);
44 }
45 };
46
47 // Start the DFS traversal with root node and initial depth of 0
48 dfs(root, 0);
49
50 // After traversal, return the found maximum height of the tree
51 return maxHeight;
52}
53
Time and Space Complexity
Time Complexity
The provided code performs a depth-first search (DFS) on a tree. During the DFS, each node is visited exactly once. For a tree with n
nodes, the time complexity is O(n)
, since every node is checked to determine its height.
However, the code also includes additional conditional checks that are intended to avoid moving in cycles (like a check to see if root.left.right != root
and root.right.left != root
). But since this is a binary tree, these checks are unnecessary and do not impact the overall time complexity. They are supposed to validate that we do not move back to the parent, yet by the nature of binary trees, this condition is redundant; hence the time complexity remains O(n)
.
Space Complexity
The space complexity of the code is primarily affected by the recursive DFS, which uses space on the call stack proportional to the height of the tree for its execution context. In the worst case (a completely unbalanced tree), the space complexity would be O(n)
. However, in a balanced tree, the space complexity would be O(log n)
due to the reduced height of the tree. The variable ans
used to maintain the maximum depth does not significantly contribute to space complexity.
Moreover, the space complexity is also influenced by the environment in which python functions execute. The usage of the nonlocal
keyword allows the DFS
internal function to modify a variable in its enclosing scope (ans
in this case), but it does not add to space complexity.
To summarize, the space complexity is O(n)
in the worst case and O(log n)
in the average or best case (balanced tree).
In a binary min heap, the minimum element can be found in:
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!