## Algorithm

We can solve this problem using a recursive algorithm which will be used to traverse the binary tree. This traversal is similar to depth-first search in the graph algorithm. Let us understand this algorithm with the help of the code given below:

```
#include<iostream>
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node(int x){
val = x; Node* left = NULL; Node*right = NULL;
}
};
int maxDepth(Node* root) {
// this is the base case when root is null we simply return 0
if(root == NULL)return 0;
// here we are computing max height that is present in the left and
// right subtree, We are adding one for the current node.
else return max( maxDepth(root->left), maxDepth(root->right) + 1 );
}
int main()
{
// constructing the tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->right = new Node(4);
root->right->right = new Node(5);
root->left->right->right = new Node(6);
root->left->right->right->right = new Node(7);
int height = maxDepth(root);
cout<<"The height of a binary tree is: "<<height<<endl;
return 0;
}
```

**Output :**

`The height of a binary tree is: 5`

**Time Complexity - O(N)**, as we are traversing every node once, the time complexity to compute the height of a binary tree is of the order N, where N is the number of nodes present in the tree.

**Space Complexity -**The space complexity is **O(H)**, where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

This problem given above can be modified as - Given the nodeâ€™s address, we have to find the height of that particular node in the tree. We can simply find the given node and start traversing to the left and right. The function to compute the following is :

## Modified Height of a binary tree

```
#include<iostream>
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node(int x){
val = x; Node* left = NULL; Node*right = NULL;
}
};
// this function is similar to maxDepth function above
int Solve(Node*root){
if(root == NULL)return 0;
else return 1 + max( Solve(root->left), Solve(root->right) );
}
// function to find the address where data is present
void find(Node *root, int data){
if(root == NULL)return;
if(root->val == data){
cout<<"The height of a binary tree is: "<<Solve(root)<<endl;
}
find(root->left, data);
find(root->right, data);
}
int main()
{
// constructing the tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->right = new Node(4);
root->right->right = new Node(5);
root->left->right->right = new Node(6);
root->left->right->right->right = new Node(7);
find(root, 4);
return 0;
}
```

**Output :**

`The height of a binary tree is: 3`

Time Complexity - **O(N)**, as we are traversing every node once, the time complexity to compute the height of a binary tree is N, where N is the number of nodes present in the tree.

Space Complexity - The space complexity is **O(H)**, where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

Check out this problem - __Mirror A Binary Tree__

## Depth of a node in a binary tree

Now let us calculate the depth of a node in a binary tree -

We can simply calculate the depth of the tree by subtracting the height of the given node by the height of the root node. i.e -

**Height(root) - Height(given node) **

We can also calculate the depth of the binary tree by applying the recursive algorithm. We initiate the depth to be 0 initially when we are present at the root node. On every recursive call we add one to the depth and return when the given element for which depth has to be calculated is equal to the current element.

```
#include<iostream>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
Node(int x){
data = x; Node* left = NULL; Node*right = NULL;
}
};
int maxDepth(Node * root, int val, int depth)
{
// Root being null means tree doesn't exist.
if (root == NULL)
return 0;
if(root->data == val)return depth;
// Get the depth of the left and right subtree
// using recursion.
int leftDepth = maxDepth(root->left, val, depth + 1);
int rightDepth = maxDepth(root->right, val, depth + 1);
// if any of the subtree does not contain the element then it will return
// null and we will simply return the value from the other tree.
return max(leftDepth, rightDepth);
}
int main()
{
// constructing the tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->right = new Node(4);
root->right->right = new Node(5);
root->left->right->right = new Node(6);
root->left->right->right->right = new Node(7);
int val = 4;
int depth = maxDepth(root, val, 1);
cout<<"The depth of a binary tree node " <<val << " is: "<<depth<<endl;
return 0;
}
```

**Output :**

`The depth of a binary tree is: 3`

Time Complexity - **O(N)**, as we are traversing every node once, the time complexity to compute the height of a binary tree is N, where N is the number of nodes present in the tree. In the worst case, our node will be a leaf node and we will end up traversing all the nodes.

Space Complexity - The space complexity is **O(H)**, where H is the height of the binary tree considering the stack space used during recursion while checking for symmetric subtrees. In the worst case(skewed binary tree), H can be equal to N, where N is the number of nodes in the tree.

## Frequently Asked Questions

### What is a binary search tree?

A binary Search Tree or BST is a tree used to sort, retrieve, and search data. It is also a non-linear data structure in which the nodes are arranged in a particular order.

- The left subtree of a node has nodes that are only lesser than that nodeâ€™s key.
- The right subtree of a node has nodes that are only greater than that nodeâ€™s key.
- Each node has distinct keys, and duplicates are not allowed in the Binary Search Tree.
- The left and right subtree must also be a binary search tree.

### Is DFS & preorder traversal the same?

Preorder traversal is another variant of DFS. Depth-first-search (DFS) traverses the search tree as much as possible before proceeding to the next sibling, which is similar to pre-order traversal.

## Conclusion

In this article, we discussed the solution to achieve the height/depth of a binary tree. This is an easy recursive problem on binary trees and can be solved using a simple application of recursion. This concept is a very important topic and has applications in other questions for the binary tree data structure. You can also refer to our course on master tree data structure to understand Trees.

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!