2773. Height of Special Binary Tree

Medium

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), unless b_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), unless b_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, and d, which is the current depth from the root node to the current node.
Initialize a variable ans in the outer scope of the dfs function (using nonlocal in Python) to keep track of the maximum depth encountered during the traversal of the tree.
In the dfs function, update ans to be the maximum of its current value or the depth d.
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 depth d + 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 depth d + 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 the root of the tree and a starting depth of 0.
After the dfs function has completed the traversal, return the value of ans, 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 Evaluator

Example 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:

Now let's walk through the solution approach:

Define the helper function dfs with the root node 3 and the current depth d which is 0.
Initialize ans to 0. This will keep track of the maximum depth.
Inside dfs, compare the current depth (starting with 0 for the root) with ans, and update ans if the depth is greater.
Check the left child of node 3, which is node 2. It does not violate the special property, so we perform dfs on this node with a depth of 1 (d + 1).
Node 2 has a left child 1. Recurse dfs with node 1. The current depth is 2. Since this is a leaf, and it doesn't have a left child linking back to its parent (3), we update ans to 2.
Node 2 (left child of the root) also has a right child 4, but we don't recurse here since 4 has a right child which is 5, not 2.
Now go back to the root node 3 and check its right child, which is another node 2. Follow the same process as in steps 4 and 5. Since node 2 does not have a left child, we move to its right child 5.
We recurse on node 5 with a depth of 2. Since node 5 does not have a left child that links back to its parent (2), we check further down. We arrive at node 1, which is leaf 5'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 is 2.
We return ans as the final answer, so in this case, the height of the tree is 2.

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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know