Implement a function recursively to get the desired Fibonacci sequence value. Your code should have the same input/output as the iterative code in the instructions.
defreverse(lines):return"Reverse order: "+ lines[::-1]+"\n"+"Normal Order: "+ linesprint(reverse("I am printing a sentence in reverse order"))print(reverse("printing strings in reverse order using python"))
defget_fib(position): output =0if(position==0):return outputif(position==1):return positionelse: output +=get_fib(position-1)+get_fib(position-2)return output# Test casesprintget_fib(9)printget_fib(11)printget_fib(0)
Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below pseudo code and program for details.
Algorithm:
maxDepth()
1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth
See the below diagram for more clarity about execution of the recursive function maxDepth() for above example tree.
# Python3 program to find the maximum depth of tree# A binary tree nodeclassNode:# Constructor to create a new nodedef__init__(self,data): self.data = data self.left =None self.right =None# Compute the "maxDepth" of a tree -- the number of nodes # along the longest path from the root node down to the # farthest leaf nodedefmaxDepth(node):if node isNone:return0 ; else:# Compute the depth of each subtree lDepth =maxDepth(node.left) rDepth =maxDepth(node.right)# Use the larger oneif (lDepth > rDepth):return lDepth+1else:return rDepth+1# Driver program to test above functionroot =Node(1)root.left =Node(2)root.right =Node(3)root.left.left =Node(4)root.left.right =Node(5)print ("Height of tree is %d"%(maxDepth(root)))# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Javascript
<script>// JavaScript program to find height of tree// A binary tree nodeclass Node{constructor(item) { this.data=item; this.left=this.right=null; }} let root; /* Compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.*/ function maxDepth(node) {if (node ==null) return 0; else {/* compute the depth of each subtree */ let lDepth =maxDepth(node.left); let rDepth =maxDepth(node.right);/* use the larger one */if (lDepth > rDepth)return (lDepth + 1); elsereturn (rDepth + 1); } } /* Driver program to test above functions */ root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); document.write("Height of tree is : " + maxDepth(root));// This code is contributed by rag2127</script>
Output
Height of tree is 2
Time Complexity: O(n) (Please see our post Tree Traversal for details)
Method 2: Another method to solve this problem is to do Level Order Traversal. While doing the level order traversal, while adding Nodes at each level to Queue, we have to add NULL Node so that whenever it is encountered, we can increment the value of variable and that level get counted.
Implementation:Python3
#include <iostream>#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node{int key; struct Node* left,*right;};// Utility function to create a new nodeNode*newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL;return(temp);}/*Function to find the height(depth) of the tree*/intheight(struct Node* root){//Initialising a variable to count the //height of treeint depth = 0; queue<Node*>q;//Pushing first level element along with NULL q.push(root); q.push(NULL);while(!q.empty()){ Node* temp = q.front(); q.pop();//When NULL encountered, increment the valueif(temp == NULL){ depth++;}//If NULL not encountered, keep movingif(temp != NULL){if(temp->left){ q.push(temp->left);}if(temp->right){ q.push(temp->right);}}//If queue still have elements left,//push NULL again to the queue.elseif(!q.empty()){ q.push(NULL);}}return depth;}// Driver programintmain(){// Let us create Binary Tree shown in above example Node *root = newNode(1); root->left = newNode(12); root->right = newNode(13); root->right->left = newNode(14); root->right->right = newNode(15); root->right->left->left = newNode(21); root->right->left->right = newNode(22); root->right->right->left = newNode(23); root->right->right->right = newNode(24); cout<<"Height(Depth) of tree is: "<<height(root);}