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.

The letter 'l' stands for leaf.

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:

When tree[i] = 'l' or I >= strlen, return 0; otherwise, return 1. (tree)

left subtree find depth(tree[i++])

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.

Frequently Asked Questions

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 tree, an introduction to binary tree, and binary search tree.