Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Complete the postOrder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values.
Input Format
Our test code passes the root node of a binary tree to the postOrder function.
Constraints
1 <= Nodes in the tree <= 500
Output Format
Print the tree's postorder traversal as a single line of space-separated values.
Sample Input
1
\
2
\
5
/ \
3 6
\
4
Sample Output
4 3 6 5 2 1
Explanation
The postorder traversal is shown.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* insert( struct node* root, int data ) {
if(root == NULL) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
} else {
struct node* cur;
if(data < = root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}
/* you only have to complete the function given below.
node is defined as
struct node {
int data;
struct node *left;
struct node *right;
};
*/
void postOrder( struct node *root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
int main() {
struct node* root = NULL;
int t;
int data;
scanf("%d", &t);
while(t-- > 0) {
scanf("%d", &data);
root = insert(root, data);
}
postOrder(root);
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
class Solution {
public:
Node* insert(Node* root, int data) {
if(root == NULL) {
return new Node(data);
} else {
Node* cur;
if(data < = root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}
void postOrder(Node *root) {
if(root == NULL)
return;
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
}; //End of Solution
int main() {
Solution myTree;
Node* root = NULL;
int t;
int data;
std::cin >> t;
while(t-- > 0) {
std::cin >> data;
root = myTree.insert(root, data);
}
myTree.postOrder(root);
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.*;
import java.io.*;
class Node {
Node left;
Node right;
int data;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class Solution {
public static void postOrder(Node root) {
Node t = root;
Deque < Node> stack = new ArrayDeque();
stack.push(root);
while(!stack.isEmpty() && root!=null){
root = stack.peek();
//nodes without children should be printed
if( (root.left==null&&root.right==null)
|| (t==root.left||t==root.right) ){//or nodes whose children have already been printed
System.out.print(root.data+" ");
stack.pop();
t = root;
}else{
if(root.right!=null) stack.push(root.right);
if(root.left!=null) stack.push(root.left);
}
}
}
public static Node insert(Node root, int data) {
if(root == null) {
return new Node(data);
} else {
Node cur;
if(data <= root.data) {
cur = insert(root.left, data);
root.left = cur;
} else {
cur = insert(root.right, data);
root.right = cur;
}
return root;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt(>;
Node root = null;
while(t-- > 0) {
int data = scan.nextInt();
root = insert(root, data);
}
scan.close();
postOrder(root);
}
}
#4 Code Example with Python Programming
Code -
Python Programming
class Node:
def __init__(self, info):
self.info = info
self.left = None
self.right = None
self.level = None
def __str__(self):
return str(self.info)
class BinarySearchTree:
def __init__(self):
self.root = None
def create(self, val):
if self.root == None:
self.root = Node(val)
else:
current = self.root
while True:
if val < current.info:
if current.left:
current = current.left
else:
current.left = Node(val)
break
elif val > current.info:
if current.right:
current = current.right
else:
current.right = Node(val)
break
else:
break
"""
Node is defined as
self.left (the left child of the node)
self.right (the right child of the node)
self.info (the value of the node)
"""
def postOrder(root):
if root.left:
postOrder(root.left)
if root.right:
postOrder(root.right)
print(root.info, end=" ")
tree = BinarySearchTree()
t = int(input())
arr = list(map(int, input().split()))
for i in range(t):
tree.create(arr[i])
postOrder(tree.root)