Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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.

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 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!

Previous article
Symmetric Binary Tree
Next article
Construct a Binary Tree from a given Preorder and Inorder traversal
Live masterclass