GeezerVison is showing github.com — Java/Programs/BinaryTreeInorder.java at main · am-opensource-learner-void/Java

Expand file tree

BinaryTreeInorder.java

Copy path

More file actions

Latest commit

History

122 lines (94 loc) · 3.13 KB

BinaryTreeInorder.java

Copy path

File metadata and controls

122 lines (94 loc) · 3.13 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

//Contributed by Dev jr - https://github.com/Dev-jr-8

class Solution {

// Function to return a list containing the inorder traversal of the tree.

ArrayList<Integer> inOrder(Node root) {

//New ArrayList to return

ArrayList<Integer> li = new ArrayList<Integer>();

travel(root, li);

return li;

}

public static void travel(Node root, ArrayList<Integer> ans)

{

if(root==null) return;

//if there is node on left, go there

if(root.left!=null)travel(root.left,ans);

//add the element to list

ans.add(root.data);

//if there is node on right, go there

if(root.right!=null)travel(root.right,ans);

}

//Time Complexity : o(n)

//Space Complexity : o(n)

//Driver Code to test the Above Class

import java.util.LinkedList;

import java.util.Queue;

import java.io.*;

import java.util.*;

class Node {

int data;

Node left;

Node right;

Node(int data) {

this.data = data;

left = null;

right = null;

}

class GfG {

static Node buildTree(String str) {

if (str.length() == 0 || str.charAt(0) == 'N') {

return null;

}

String ip[] = str.split(" ");

// Create the root of the tree

Node root = new Node(Integer.parseInt(ip[0]));

// Push the root to the queue

Queue<Node> queue = new LinkedList<>();

queue.add(root);

// Starting from the second element

int i = 1;

while (queue.size() > 0 && i < ip.length) {

// Get and remove the front of the queue

Node currNode = queue.peek();

queue.remove();

// Get the current node's value from the string

String currVal = ip[i];

// If the left child is not null

if (!currVal.equals("N")) {

// Create the left child for the current node

currNode.left = new Node(Integer.parseInt(currVal));

// Push it to the queue

queue.add(currNode.left);

}

// For the right child

i++;

if (i >= ip.length) break;

currVal = ip[i];

// If the right child is not null

if (!currVal.equals("N")) {

// Create the right child for the current node

currNode.right = new Node(Integer.parseInt(currVal));

// Push it to the queue

queue.add(currNode.right);

}

i++;

}

return root;

}

public static void main(String[] args) throws IOException {

BufferedReader br =

new BufferedReader(new InputStreamReader(System.in));

int t = Integer.parseInt(br.readLine());

while (t > 0) {

String s = br.readLine();

Node root = buildTree(s);

Solution g = new Solution();

ArrayList<Integer> res = g.inOrder(root);

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

System.out.print(res.get(i) + " ");

System.out.print("\n");

t--;

}