In this HackerRank Tree: Postorder Traversal problem we have given a pointer to the root node of a binary tree. and we need to print the values of trees in postorder in a single line.
Problem solution in 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
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)
Problem solution in 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<Node>(); 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); } }
Problem solution in 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;
}
Problem solution in 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;
}
}
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;
}
0 Comments