Java Coding Test Course, Binary Tree

Problem Description

In this problem, you need to write an algorithm that stores values for each node of a binary tree and returns the height of the binary tree for a node with a specific value. The given binary tree is defined as follows:

        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }

Problem: Calculate the height for a specific value in a binary tree

You are given the root node of a binary tree and a specific value target. Return the height of the node with target in the binary tree. The height of a node is defined as the length of the longest path from that node to a leaf node. If there is no node with the target value, return -1.

Input

  • TreeNode root: the root node of the binary tree
  • int target: the value to search for

Output

  • The height of the target, or -1 if the target cannot be found

Solution Method

To solve this problem, you first need to understand and implement an algorithm to calculate the height of a binary tree. You will design the algorithm to traverse the tree using depth-first search (DFS) and find the node that matches the target value, returning the height of that node.

Step-by-Step Solution

  1. Understand the structure of a binary tree: A binary tree is a tree structure where each node can have at most two child nodes. Each node stores data.
  2. Implement depth-first search (DFS): Recursively traverse the data to find the target node.
  3. Calculate the height: When the target node is found, calculate the maximum depth from that node to a leaf.
  4. Return the result: If the target node is found, return its height; if not, return -1.

Java Code Implementation

        public class Solution {
            public int findHeight(TreeNode root, int target) {
                return findNodeHeight(root, target, 0);
            }

            private int findNodeHeight(TreeNode node, int target, int depth) {
                if (node == null) {
                    return -1; // Return -1 if the node is null
                }
                
                // If the current node is the target node
                if (node.val == target) {
                    return getHeight(node);
                }
                
                // If not a leaf node, search the child nodes
                int leftHeight = findNodeHeight(node.left, target, depth + 1);
                int rightHeight = findNodeHeight(node.right, target, depth + 1);

                // If the target node is found in the left node, return its height
                if (leftHeight != -1) {
                    return leftHeight;
                }
                // If the target node is found in the right node, return its height
                return rightHeight;
            }

            private int getHeight(TreeNode node) {
                if (node == null) return -1; // For leaf nodes, depth is -1
                
                // Recursively calculate the depth of left and right subtrees
                int leftHeight = getHeight(node.left);
                int rightHeight = getHeight(node.right);
                
                // Return the maximum depth from the current node to a leaf
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }

Code Explanation

In the code above, the findHeight method takes the root node and target value as arguments and searches for the node. findNodeHeight recursively traverses each node to find the target value and calculate its height. The getHeight method is called to calculate the depth of a specific node.

Example

Consider the following binary tree.

                  1
                 / \
                2   3
               / \
              4   5

For the binary tree, when target = 3, the height of that node is 0. When target = 2, the height is 1. When target = 4, the height is 2. For a non-existing node, it should return -1; for example, when target = 6, the result is -1.

Conclusion

In this lecture, we explored the methods for traversing a binary tree and calculating its height. Understanding and practicing these tree structures is important, as they often appear in coding tests. The more you practice algorithms, the more your thought process for solving each problem will develop, and you will gain confidence.