Give an algorithm for inserting an element into binary tree in non-recersive way

package in.blogspot.arunj2ee.ds.tree.binary.que;

import in.blogspot.arunj2ee.ds.tree.BinaryTreeNode;
import in.blogspot.arunj2ee.ds.tree.util.BTreePrinter;
import in.blogspot.arunj2ee.ds.tree.util.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;

/*
 * Que: Give an algorithm for inserting an element into binary tree in non-recersive way
 * Time complexity: O(n), Space Complexity: O(n)
 */
public class Que5a {
public static BinaryTreeNode insertInBinaryTreeLevelOrder(
BinaryTreeNode root, int data) {
if (root == null)
return new BinaryTreeNode(data);

Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
q.offer(root);

while (!q.isEmpty()) {
BinaryTreeNode tmp = q.poll();

if (tmp != null) {
if (tmp.getLeft() != null)
q.offer(tmp.getLeft());
else {
tmp.setLeft(new BinaryTreeNode(data));
return root;
}

if (tmp.getRight() != null)
q.offer(tmp.getRight());
else {
tmp.setRight(new BinaryTreeNode(data));
return root;
}
}
}

return root;
}

public static void main(String[] args) {
BinaryTreeNode rootNode = TreeUtil.createRandomBinaryTree();
BTreePrinter.printBinaryTreeNode(rootNode);
insertInBinaryTreeLevelOrder(rootNode, 500);
BTreePrinter.printBinaryTreeNode(rootNode);
}
}

========================================================================

Refer Core Classes: http://arunj2ee.blogspot.in/2017/05/tree-core-and-utility-classes.html
========================================================================

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.