Calculate depth of a full Binary tree from Preorder

Last Updated : 11 Sep, 2023

Given preorder of a binary tree, calculate its depth(or height) [starting from depth 0]. The preorder is given as a string with two possible characters.

‘l’ denotes the leaf
‘n’ denotes internal node

The given tree can be seen as a full binary tree where every node has 0 or two children. The two children of a node can ‘n’ or ‘l’ or mix of both.

Examples :

Input  : nlnll
Output : 2
Explanation :

Input  : nlnnlll
Output : 3

Preorder of the binary tree is given so traverse

Also, we would be given a string of char (formed of ‘n’ and ‘l’), so there is no need to implement tree also.

The recursion function would be:

Base Case: return 0; when tree[i] = ‘l’ or i >= strlen(tree)
find_depth( tree[i++] ) //left subtree
find_depth( tree[i++] ) //right subtree

Where i is the index of the string tree.

Implementation:

C++

// C++ program to find height of full binary tree 
// using preorder 
#include <bits/stdc++.h> 
using namespace std; 
  
// function to return max of left subtree height 
// or right subtree height 
int findDepthRec(char tree[], int n, int& index) 
{ 
    if (index >= n || tree[index] == 'l') 
        return 0; 
  
    // calc height of left subtree (In preorder 
    // left subtree is processed before right) 
    index++; 
    int left = findDepthRec(tree, n, index); 
  
    // calc height of right subtree 
    index++; 
    int right = findDepthRec(tree, n, index); 
  
    return max(left, right) + 1; 
} 
  
// Wrapper over findDepthRec() 
int findDepth(char tree[], int n) 
{ 
    int index = 0; 
    return findDepthRec(tree, n, index); 
} 
  
// Driver program 
int main() 
{ 
    // Your C++ Code 
    char tree[] = "nlnnlll"; 
    int n = strlen(tree); 
  
    cout << findDepth(tree, n) << endl; 
  
    return 0; 
} 

Java

// Java program to find height  
// of full binary tree using 
// preorder 
import java .io.*; 
  
class GFG  
{ 
    // function to return max  
    // of left subtree height 
    // or right subtree height 
    static int findDepthRec(String tree,  
                            int n, int index) 
    { 
        if (index >= n ||  
            tree.charAt(index) == 'l') 
            return 0; 
  
        // calc height of left subtree  
        // (In preorder left subtree  
        // is processed before right) 
        index++; 
        int left = findDepthRec(tree,  
                                n, index); 
  
        // calc height of 
        // right subtree 
        index++; 
        int right = findDepthRec(tree, n, index); 
  
        return Math.max(left, right) + 1; 
    } 
  
    // Wrapper over findDepthRec() 
    static int findDepth(String tree, 
                         int n) 
    { 
        int index = 0; 
        return (findDepthRec(tree,  
                             n, index)); 
    } 
  
    // Driver Code 
    static public void main(String[] args) 
    { 
        String tree = "nlnnlll"; 
        int n = tree.length(); 
        System.out.println(findDepth(tree, n)); 
    } 
} 
  
// This code is contributed 
// by anuj_67. 

Python3

#Python program to find height of full binary tree  
# using preorder 
      
# function to return max of left subtree height  
# or right subtree height  
def findDepthRec(tree, n, index) : 
  
    if (index[0] >= n or tree[index[0]] == 'l'): 
        return 0
  
    # calc height of left subtree (In preorder  
    # left subtree is processed before right)  
    index[0] += 1
    left = findDepthRec(tree, n, index)  
  
    # calc height of right subtree  
    index[0] += 1
    right = findDepthRec(tree, n, index) 
    return (max(left, right) + 1) 
  
# Wrapper over findDepthRec()  
def findDepth(tree, n) : 
  
    index = [0]  
    return findDepthRec(tree, n, index)  
  
          
# Driver program to test above functions  
if __name__ == '__main__': 
    tree= "nlnnlll"
    n = len(tree)  
  
    print(findDepth(tree, n)) 
  
# This code is contributed by SHUBHAMSINGH10 

C#

// C# program to find height of 
// full binary tree using preorder 
using System; 
  
class GFG { 
  
    // function to return max of left subtree 
    // height or right subtree height 
    static int findDepthRec(char[] tree, int n, int index) 
    { 
        if (index >= n || tree[index] == 'l') 
            return 0; 
  
        // calc height of left subtree (In preorder 
        // left subtree is processed before right) 
        index++; 
        int left = findDepthRec(tree, n, index); 
  
        // calc height of right subtree 
        index++; 
        int right = findDepthRec(tree, n, index); 
  
        return Math.Max(left, right) + 1; 
    } 
  
    // Wrapper over findDepthRec() 
    static int findDepth(char[] tree, int n) 
    { 
        int index = 0; 
        return (findDepthRec(tree, n, index)); 
    } 
  
    // Driver program 
    static public void Main() 
    { 
        char[] tree = "nlnnlll".ToCharArray(); 
        int n = tree.Length; 
        Console.WriteLine(findDepth(tree, n)); 
    } 
} 
  
// This code is contributed by vt_m. 

Javascript

<script> 
    // Javascript program to find height of 
    // full binary tree using preorder 
      
    // function to return max of left subtree 
    // height or right subtree height 
    function findDepthRec(tree, n, index) 
    { 
        if (index >= n || tree[index] == 'l') 
            return 0; 
   
        // calc height of left subtree (In preorder 
        // left subtree is processed before right) 
        index++; 
        let left = findDepthRec(tree, n, index); 
   
        // calc height of right subtree 
        index++; 
        let right = findDepthRec(tree, n, index); 
   
        return Math.max(left, right) + 1; 
    } 
   
    // Wrapper over findDepthRec() 
    function findDepth(tree, n) 
    { 
        let index = 0; 
        return (findDepthRec(tree, n, index)); 
    } 
      
    let tree = "nlnnlll".split(''); 
    let n = tree.length; 
    document.write(findDepth(tree, n)); 
      
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

S

Shubham Gupta

Improve

Previous Article

Boundary Traversal of binary tree

Construct a tree from Inorder and Level order traversals | Set 1

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Construct Full Binary Tree from given preorder and postorder traversals

Given two arrays that represent preorder and postorder traversals of a full binary tree, construct the binary tree. Full Binary Tree is a binary tree where every node has either 0 or 2 children. Illustration: Following are examples of Full Trees. 1 / \ 2 3 / \ / \ 4 5 6 7 1 / \ 2 3 / \ 4 5 / \ 6 7 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 It is not possibl

Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree

cGiven two arrays pre[] and in[] representing the preorder and inorder traversal of the binary tree, the task is to check if the given traversals are valid for any binary tree or not without building the tree. If it is possible, then print Yes. Otherwise, print No. Examples: Input: pre[] = {1, 2, 4, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}Ou

Construct the full k-ary tree from its preorder traversal

Given an array that contains the preorder traversal of the full k-ary tree, construct the full k-ary tree and print its postorder traversal. A full k-ary tree is a tree where each node has either 0 or k children. Examples: Input : preorder[] = {1, 2, 5, 6, 7, 3, 8, 9, 10, 4} k = 3 Output : Postorder traversal of constructed full k-ary tree is: 5 6

Leaf nodes from Preorder of a Binary Search Tree (Using Recursion)

Given Preorder traversal of a Binary Search Tree. Then the task is to print leaf nodes of the Binary Search Tree from the given preorder. Examples : Input : preorder[] = {890, 325, 290, 530, 965}; Output : 290 530 965 Tree represented is, 890 / \ 325 965 / \ 290 530 Input : preorder[] = { 3, 2, 4 }; Output : 2 4 In this post, a simple recursive sol

Modify a binary tree to get preorder traversal using right pointers only

Given a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only the right pointers. During modification, you can use right as well as left pointers. Examples: Input : 10 / \ 8 2 / \ 3 5 Output : 10 \ 8 \ 3 \ 5 \ 2 Explanation : The preorder traversal of given binary tree is 10 8 3 5 2. Method

Find n-th node in Preorder traversal of a Binary Tree

Given a Binary tree and a number N, write a program to find the N-th node in the Preorder traversal of the given Binary tree. Prerequisite: Tree Traversal Examples: Input: N = 4 11 / \ 21 31 / \ 41 51 Output: 51 Explanation: Preorder Traversal of given Binary Tree is 11 21 41 51 31, so 4th node will be 51. Input: N = 5 25 / \ 20 30 / \ / \ 18 22 24

Preorder, Postorder and Inorder Traversal of a Binary Tree using a single Stack

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order iteratively using only one stack traversal. Examples: Input: Output:Preorder Traversal: 1 2 3Inorder Traversal: 2 1 3Postorder Traversal: 2 3 1 Input: Output:Preorder traversal: 1 2 4 5 3 6 7Inorder traversal: 4 2 5 1 6 3 7Post-order tr

Modify Binary Tree by replacing each node with the sum of its Preorder Predecessor and Successor

Given a binary tree consisting of N nodes, the task is to replace each node in the binary tree with the sum of its preorder predecessor and preorder successor. Examples: Input: 2 / \ 3 4 / \ / \ 6 5 7 8 Output: 3 / \ 8 12 / \ / \ 8 10 12 7 Explanation: For Node 2: Preorder predecessor = 0 (as preorder predecessor is not present), preorder successor

Article Tags :

DSA
Tree

Practice Tags :

Tree