Array ( [0] => [1] => questions [2] => Popular-Algorithms [3] => Binary-Search-Tree-Traversal-Techniques )
Given an array of integers. convert the array to a binary search tree and perform inorder , preorder and post order traversal on it
First Line contains no of elements in the array Next line contains n elements representing the array elements
Print the inorder, preorder and postorder traversal of the tree.
5 3 2 1 4 5
1 2 3 4 5 3 2 1 4 5 1 2 5 4 3
8 5 7 2 1 8 6 3 5
1 2 3 5 5 6 7 8 5 2 1 3 5 7 6 8 1 5 3 2 6 8 7 5
10 55 21 4 2 5 36 25 78 26 33
2 4 5 21 25 26 33 36 55 78 55 21 4 2 5 36 25 26 33 78 2 5 4 33 26 25 36 21 78 55
Login to see Discussion
Step-i) Create a class Node with instances data of int type and left,right of Node type
Step-ii)create a default constructor which initializes left and right to null
Step-iii)create a constructor which accepts key as argument and assigns it to data
(this class is used to create a node of the tree)
Step-iv)create another class binary tree
Step-v)create a public method which return Node and takes root,node of Node type as arguments
Step-vi)if root is null assign node to root and return node
Step-vii)if data of root is less than data of node go to next step else go to ix
Step-viii)if right of root is null assign node to root right else call the insert method passing root.right and node as argument
Step-ix)if left of root is null assign node to root left else call the insert method passing root.left and node as argument
Step-x)return root
(now we are done with the insert method)
Step-xi)create a void method inorder which accepts root of Node type as argument
Step-xii)if root is null just return
Step-xiii)call inorder method passing root.left as argument
Step-xiv)print the data present in root.data
Step-xv)call inorder method passing root.right as argument
(we are done with inorder method)
Step-xvi)create a void method preorder which accepts root of Node type as argument
Step-xvii)if root is null just return
Step-xviii) print the data present in root.data
Step-xix)call the preorder function passing root.left as an argument
Step-xx)call the preorder function passing root.right as an argument
(we are done with pre order method)
Step-xxi)create a void method post order which accepts root of Node type as argument
Step-xxii)if root is null just return
Step-xxiii)call the postorder method passing root.left as an argument
Step-xxiv)call the postorder method passing root.right as an argument
Step-xxv)print the data present in the root.data
(we are done with the post order method)
Step-xxvi)now create the main method
Step-xxvii)take the input n which tells the no of elements in the array
Step-xxviii)read n numbers and store it in the array
Step-xxix)traverse the array and pass it's values to the insert method to construct the binary tree
Step-xxx)call the inorder method passing root as argument
Step-xxxi)call the preorder method passing root as argument
Step-xxxii)call the postorder method passing root as argument
Time Complexity: O(n)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution