Depth of a full Binary tree from Preorder

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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
	}
}

You can also try this code with Online Java Compiler

Run Code

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.

Recommended Problems:

• Burn Tree
• Size of largest BST in a Binary Tree.
• Partial BST
   

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!