find height of a tree | Code Ease (2024)

Solution 1:

Certainly! To find the height of a tree in C++, you can use a recursive approach. Here's a simple example of how you can implement this:

cpp
#include <iostream>
#include <algorithm> // for max function
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
 int val;
 TreeNode* left;
 TreeNode* right;
 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Function to find the height of a binary tree
int findHeight(TreeNode* root) {
 // Base case: if the tree is empty, height is 0
 if (root == nullptr) {
 return 0;
 }
 // Recursive cases: find height of left and right subtrees
 int leftHeight = findHeight(root->left);
 int rightHeight = findHeight(root->right);
 // Return the maximum height of left and right subtrees, plus 1 for the current level
 return 1 + max(leftHeight, rightHeight);
}
int main() {
 // Example tree
 TreeNode* root = new TreeNode(1);
 root->left = new TreeNode(2);
 root->right = new TreeNode(3);
 root->left->left = new TreeNode(4);
 root->left->right = new TreeNode(5);
 root->right->left = new TreeNode(6);
 root->right->right = new TreeNode(7);
 // Call the function to find the height
 int height = findHeight(root);
 // Output the result
 cout << "Height of the tree is: " << height << endl;
 // Clean up memory (optional)
 delete root->left->left;
 delete root->left->right;
 delete root->right->left;
 delete root->right->right;
 delete root->left;
 delete root->right;
 delete root;
 return 0;
}

In this example, the findHeight function takes the root of the binary tree as an argument and recursively calculates the height. The main function creates a sample binary tree and calls the findHeight function to get the height, which is then printed to the console. Make sure to clean up memory by deleting the tree nodes after use.

Feel free to modify the tree structure and values based on your requirements.

Solution 2:

## In-depth explanation of finding height of a tree in C++

A tree is a hierarchical data structure, where each node has a parent node and zero or more child nodes. The height of a tree is the number of edges from the root node to the deepest leaf node.

To find the height of a tree, we can use a recursive algorithm. The algorithm starts at the root node and recursively calculates the height of each child node. The height of a node is the maximum of the heights of its child nodes plus one. The height of the tree is the height of the root node.

Here is an example of a tree with the following nodes:

 A
 / \
 B C
 / \ / \
D E F G

The height of this tree is 3, because the longest path from the root node to a leaf node is 3 edges long.

Here is the recursive algorithm for finding the height of a tree in C++:

c++
int height(Node* node) {
 if (node == nullptr) {
 return 0;
 }
 int max_height = 0;
 for (Node* child : node->children) {
 max_height = std::max(max_height, height(child));
 }
 return max_height + 1;
}

Here is an example of how to use this algorithm to find the height of the tree shown above:

c++
Node* root = new Node("A");
root->children.push_back(new Node("B"));
root->children.push_back(new Node("C"));
root->children[0]->children.push_back(new Node("D"));
root->children[0]->children.push_back(new Node("E"));
root->children[1]->children.push_back(new Node("F"));
root->children[1]->children.push_back(new Node("G"));
int height = height(root);
// height = 3

## Code examples

Here are some code examples of finding the height of a tree in C++:

c++
// Find the height of a binary tree.
int height(Node* root) {
 if (root == nullptr) {
 return 0;
 }
 int left_height = height(root->left);
 int right_height = height(root->right);
 return std::max(left_height, right_height) + 1;
}
// Find the height of a general tree.
int height(Node* root) {
 if (root == nullptr) {
 return 0;
 }
 int max_height = 0;
 for (Node* child : root->children) {
 max_height = std::max(max_height, height(child));
 }
 return max_height + 1;
}

## Outputs

Here are some outputs of finding the height of a tree in C++:

// Binary tree with height 3.
int height = height(root);
// height = 3
// General tree with height 4.
int height = height(root);
// height = 4

Solution 3:

In order to find the height of a tree in C++, we first need to define what a tree is. For the purpose of this answer, we will use a binary tree, where each node has at most two children. The height of a tree is defined as the number of edges on the longest path from the root to a leaf node. Here is an example of how to find the height of a binary tree in C++:

First, let's define the structure of a tree node:

c
struct TreeNode {
 int data;
 TreeNode* left;
 TreeNode* right;
 TreeNode(int data) : data(data), left(nullptr), right(nullptr) {}
};

Each node has an integer value, as well as two pointers to its left and right children.

Next, we can define a function to find the height of a tree:

c
int height(TreeNode* node) {
 if (node == nullptr) {
 return -1; // by convention, the height of an empty tree is -1
 }
 int leftHeight = height(node->left);
 int rightHeight = height(node->right);
 // the height of the tree is the maximum of the heights of its children, plus 1 (for the root node)
 return std::max(leftHeight, rightHeight) + 1;
}

This function recursively traverses the tree, calculating the height of each subtree and returning the maximum value plus 1.

Here is an example of how to use this function to find the height of a tree:

c
int main() {
 // create a tree with the following structure:
 // 1
 // / \
 // 2 3
 // / \ / \
 // 4 5 6 7
 TreeNode* root = new TreeNode(1);
 root->left = new TreeNode(2);
 root->right = new TreeNode(3);
 root->left->left = new TreeNode(4);
 root->left->right = new TreeNode(5);
 root->right->left = new TreeNode(6);
 root->right->right = new TreeNode(7);
 int treeHeight = height(root);
 std::cout << "The height of the tree is: " << treeHeight << std::endl; // outputs: The height of the tree is: 3
 return 0;
}

This code creates a binary tree with 7 nodes and finds its height using the height function defined earlier. The output of the program is The height of the tree is: 3, which is the number of edges on the longest path from the root to a leaf node (i.e., the path from the root node with value 1 to the leaf node with value 7).