Find postorder traversal of a binary tree from its inorder and preorder sequence

Write an efficient algorithm to find postorder traversal on a given binary tree from its inorder and preorder sequence.

For example, consider the following tree:

Print Binary Tree

Input:

Inorder traversal is { 4, 2, 1, 7, 5, 8, 3, 6 }
Preorder traversal is { 1, 2, 4, 3, 5, 7, 8, 6 }

Output:

Postorder traversal is 4 2 7 8 5 6 3 1

Practice this problem

A simple solution would be to construct the binary tree from the given inorder and preorder sequences and then print the postorder traversal by traversing the tree.

We can avoid constructing the tree by passing some extra information in a recursive postorder call. In a simple recursive postorder call, the left subtree is processed first, followed by the right subtree, and finally, the node is printed. We can perform something similar for printing the postorder traversal.

The idea is to start with the root node, whose value would be the first item in the preorder sequence. We find boundaries of the left and right subtree of the current root node in the inorder sequence. To find the left and right subtree boundaries, search for the root node index in the inorder sequence. All keys before the root node in the inorder sequence become part of the left subtree, and all keys after the root node become part of the right subtree. If we repeat this recursively for all tree nodes, we will end up doing a postorder traversal on the tree. This algorithm is demonstrated below in C++, Java, and Python:

C++

#include <iostream>

#include <vector>

#include <unordered_map>

using namespace std;

// Recursive function to find postorder traversal of a binary tree

// from its inorder and preorder sequence

void printPostorder(int start, int end,

vector<int> const &preorder, int &pIndex,

unordered_map<int, int> &map)

{

// base case

if (start > end) {

return;

}

// The next element in the preorder sequence will be the root node of

// subtree formed by sequence inorder[start, end]

int value = preorder[pIndex++];

// if the current node is a leaf node (no children)

if (start == end)

{

// print the value of the root node and return

cout << value << ' ';

return;

}

// Get the root node index in inorder sequence to determine

// its left and right subtree boundary

int i = map[value];

// recur for the left subtree

printPostorder(start, i - 1, preorder, pIndex, map);

// recur for the right subtree

printPostorder(i + 1, end, preorder, pIndex, map);

// print the value of the root node

cout << value << ' ';

}

// Find postorder traversal on a given binary tree from its inorder and

// preorder sequence. This function assumes that the input is valid.

// i.e., given inorder and preorder sequence forms a binary tree.

void findPostorder(vector<int> const &inorder, vector<int> const &preorder)

{

// create a map to efficiently find the index of any element in a

// given inorder sequence

unordered_map<int, int> map;

// fill the map

for (int i = 0; i < inorder.size(); i++) {

map[inorder[i]] = i;

}

// `pIndex` stores the index of the next unprocessed node in the preorder sequence.

// start with the root node (present at 0th index)

int pIndex = 0;

cout << "Postorder traversal is ";

printPostorder(0, inorder.size() - 1, preorder, pIndex, map);

}

int main()

{

/* Construct the following tree

/ \

2 3

/ / \

4 5 6

/ \

7 8

vector<int> inorder = { 4, 2, 1, 7, 5, 8, 3, 6 };

vector<int> preorder = { 1, 2, 4, 3, 5, 7, 8, 6 };

findPostorder(inorder, preorder);

return 0;

}

Download Run Code

Output:

Postorder traversal is 4 2 7 8 5 6 3 1

Java

import java.util.HashMap;

import java.util.Map;

import java.util.concurrent.atomic.AtomicInteger;

class Main

{

// Recursive function to find postorder traversal of a binary tree

// from its inorder and preorder sequence

public static void printPostorder(int start, int end,

int[] preorder, AtomicInteger pIndex,

Map<Integer, Integer> map)

{

// base case

if (start > end) {

return;

}

// The next element in the preorder sequence will be the root node of

// subtree formed by sequence inorder[start, end]

int value = preorder[pIndex.getAndIncrement()];

// if the current node is a leaf node (no children)

if (start == end)

{

// print the value of the root node and return

System.out.print(value + " ");

return;

}

// Get the root node index in inorder sequence to determine

// its left and right subtree boundary

int i = map.get(value);

// recur for the left subtree

printPostorder(start, i - 1, preorder, pIndex, map);

// recur for the right subtree

printPostorder(i + 1, end, preorder, pIndex, map);

// print the value of the root node

System.out.print(value + " ");

}

// Find postorder traversal on a given binary tree from its inorder and

// preorder sequence. This function assumes that the input is valid.

// i.e., given inorder and preorder sequence forms a binary tree.

public static void findPostorder(int[] inorder, int[] preorder)

{

// create a map to efficiently find the index of any element in a

// given inorder sequence

Map<Integer, Integer> map = new HashMap<>();

// fill the map

for (int i = 0; i < inorder.length; i++) {

map.put(inorder[i], i);

}

// `pIndex` stores the index of the next unprocessed node in the preorder.

// start with the root node (present at 0th index)

AtomicInteger pIndex = new AtomicInteger(0);

System.out.print("Postorder traversal is ");

printPostorder(0, inorder.length - 1, preorder, pIndex, map);

}

public static void main(String[] args)

{

/* Construct the following tree

/ \

2 3

/ / \

4 5 6

/ \

7 8

int[] inorder = { 4, 2, 1, 7, 5, 8, 3, 6 };

int[] preorder = { 1, 2, 4, 3, 5, 7, 8, 6 };

findPostorder(inorder, preorder);

}

Download Run Code

Output:

Postorder traversal is 4 2 7 8 5 6 3 1

Python

# Recursive function to find postorder traversal of a binary tree

# from its inorder and preorder sequence

def printPostorder(start, end, preorder, pIndex, d):

# base case

if start > end:

return pIndex

# The next element in the preorder sequence will be the root node of

# subtree formed by sequence inorder[start, end]

value = preorder[pIndex]

pIndex = pIndex + 1

# if the current node is a leaf node (no children)

if start == end:

# print the value of the root node and return

print(value, end=' ')

return pIndex

# Get the root node index in inorder sequence to determine

# its left and right subtree boundary

i = d[value]

# recur for the left subtree

pIndex = printPostorder(start, i - 1, preorder, pIndex, d)

# recur for the right subtree

pIndex = printPostorder(i + 1, end, preorder, pIndex, d)

# print the value of the root node

print(value, end=' ')

return pIndex

# Find postorder traversal on a given binary tree from its inorder and

# preorder sequence. This function assumes that the input is valid.

# i.e., given inorder and preorder sequence forms a binary tree.

def findPostorder(inorder, preorder):

# create a dictionary to efficiently find the index of any element in a

# given inorder sequence

d = {}

# fill the dictionary

for i, e in enumerate(inorder):

d[e] = i

# `pIndex` stores the index of the next unprocessed node in the preorder sequence.

# start with the root node (present at 0th index)

pIndex = 0

print('Postorder traversal is ', end='')

printPostorder(0, len(inorder) - 1, preorder, pIndex, d)

if __name__ == '__main__':

''' Construct the following tree

/ \

2 3

/ / \

4 5 6

/ \

7 8

'''

inorder = [4, 2, 1, 7, 5, 8, 3, 6]

preorder = [1, 2, 4, 3, 5, 7, 8, 6]

findPostorder(inorder, preorder)

Download Run Code

Output:

Postorder traversal is 4 2 7 8 5 6 3 1

The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(n) extra space for the hash table and call stack. Here‘s an implementation in C, which runs in O(n²) time.

Find postorder traversal of a binary tree from its inorder and preorder sequence

C++

Java

Python

Share this: