1.
Introduction
2.
Example
2.1.
Input
2.2.
Output
3.
Algorithm
3.1.
C++ Code
3.2.
Java Code
3.3.
Input
3.4.
Output
4.
Complexities
4.1.
Time complexity
4.2.
Space complexity
5.
5.1.
What are binary trees, and how do they work?
5.2.
What are the different types of Binary Trees?
5.3.
What is the purpose of binary trees?
5.4.
What is the best way to find the preOrder traversal?
5.5.
What is the best way to find the postOrder traversal?
6.
Conclusion
Last Updated: Mar 27, 2024

# Depth of a full Binary tree from Preorder

Manan Singhal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

Calculate a binary tree's depth (or height) given its preorder [beginning at depth 0]. The preorder is specified as a string of two characters.

1. The letter 'l' stands for leaf.
2. The letter 'n' stands for internal node.

The given tree can be viewed as a full binary tree with 0 or 2 children for each node. A node's two children can be 'n' or 'l' or a mix of both.

## Example

### Input

``nlnll``

### Output

``2``
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Algorithm

The binary tree's preorder is known. Therefore, traverse it.

There is no need to implement a tree because we will be provided a string of char (made of 'n' and 'l').

The recursive function would be as follows:

1.  When tree[i] = 'l' or I >= strlen, return 0; otherwise, return 1. (tree)
2. left subtree find depth(tree[i++])
3. right subtree(tree[i++]) find depth(tree[i++])

where, i is the index of the string given.

### C++ Code

``````/* C++ program to find the depth of a full binary tree from preorder */
#include <bits/stdc++.h>

using namespace std;

/* function to return max of left subtree height or right subtree height */
int findDepthRecursion(char tree[], int n, int& index)
{
if (index >= n || tree[index] == 'l')
return 0;

/* calculate height of left subtree */
index++;
int left = findDepthRecursion(tree, n, index);

/* calculate height of right subtree */
index++;
int right = findDepthRecursion(tree, n, index);

return max(left, right) + 1;
}

int findDepth(char tree[], int n)
{
int index = 0;
return findDepthRecursion(tree, n, index);
}

int main()
{
char tree[] = "nlnll";
int n = strlen(tree);

cout << findDepth(tree, n) << endl;

return 0;
}``````

### Java Code

``````/* Java program to find the depth of a full binary tree from preorder */
import java .io.*;

class Main {
/* function to return max of left subtree height or right subtree height */
static int findDepthRecursion(String tree, int n, int index)
{
if (index >= n || tree.charAt(index) == 'l')
return 0;

/* calculate height of left subtree */
index++;
int left = findDepthRecursion(tree, n, index);

/* calculate height of right subtree */
index++;
int right = findDepthRecursion(tree, n, index);

return Math.max(left, right) + 1;
}

static int findDepth(String tree, int n)
{
int index = 0;
return (findDepthRecursion(tree, n, index));
}

static public void main(String[] args)
{
String tree = "nlnll";
int n = tree.length();
System.out.println(findDepth(tree, n));
}
}``````

### Input

``nlnll``

### Output

``2``

## Complexities

### Time complexity

O(n),
Reason: Using recursion so that the time complexity will be O(n).

### Space complexity

O(1),
Reason: No extra space required.

### What are binary trees, and how do they work?

It is a non-linear data structure of the tree type with a maximum of two offspring per parent. The root node is the node at the very top of a tree's hierarchy. The parent nodes are the nodes that include additional sub-nodes.

### What are the different types of Binary Trees?

Following are the different types of binary trees: full binary tree, perfect binary tree, skewed binary tree, complete binary tree, and degenerate binary tree.

### What is the purpose of binary trees?

Binary trees are mostly used in computing for searching and sorting since they allow data to be stored hierarchically. Insertion, deletion, and traversal are some of the most frequent operations performed on binary trees.

### What is the best way to find the preOrder traversal?

We can use the preOrder traversal's recursive definition to visit the root, recursively travel to the left subtree, and then proceed to the right subtree.

### What is the best way to find the postOrder traversal?

We can use the postOrder traversal's recursive definition to travel to the left subtree, then the right subtree, and finally the root.

## Conclusion

In this article, we have calculated the depth of a full binary tree from preorder. We hope that this blog will help you understand the concept of a binary tree, and if you would like to learn more about the binary tree, check out our other blogs on the binary treean introduction to binary tree, and binary search tree.

Recommended Problems:

Refer to our guided paths on Coding Ninjas Studio to learn more about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass