Construct Binary Tree from Inorder and Postorder/Preorder Traversal

From INORDER and POSTORDER

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Algorithm:

In Postorder, the rightmost element is the root. Search this root in inorder array .Let that index be i ,then left side of i is left subtree and right side of i is right subtree. We use postorder array to create nodes but to construct tree we use inorder array.

Code:

class Solution {
int index;
public TreeNode buildTree(int[] inorder, int[] postorder) {
index= postorder.length-1;
return build(postorder,inorder,0,postorder.length-1);
}
public TreeNode build(int[] post, int[] in, int start, int end){
if(start>end){
return null;
}
TreeNode node = new TreeNode(post[index]);
index--;

int inIndex=search(in,start,end,node.val);

node.right=build(post,in,inIndex+1,end);
node.left=build(post,in,start,inIndex-1);
return node;

}
public int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i;
}
return i;
}
}

From INORDER and PREORDER

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Code:

class Solution {
int index=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,inorder,0,preorder.length-1);
}
public TreeNode build(int[] pre, int[] in, int start, int end){
if(start>end){
return null;
}
TreeNode node = new TreeNode(pre[index]);
index++;
if(start==end){
return node;
}
int inIndex=search(in,start,end,node.val);
node.left=build(pre,in,start,inIndex-1);
node.right=build(pre,in,inIndex+1,end);
return node;

}
public int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i;
}
return i;
}
}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Python Data Types

Connecting to Binance Smart Chain

PostgreSQL with Docker — Quick Start

Amazon EKS Vlog:用StatefulSet打造Stateful Application

How to pass Security Context in Spring to child threads

Who is giving access? IAM?

https://concept-tees.myspreadshop.com/general+principle+money+wall-A5bcd5ee6205176300370b6f7

5 Years and still Mobile OSs lacks this primary feature! Wow!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhinay Gupta

Abhinay Gupta

More from Medium

Rusty IBM5251 Restoration Log

Scaaaaaaaaaalaaaability

Difference Between RAM and ROM

Your guide to Supervised Learning — Classification