Answer to Question #158962 in Java | JSP | JSF for Fareeha Nadeem

Question

Draw a binary search tree and AVL tree from the following traversals:

{15, 5, 20, 70, 3, 10, 60, 90, 16}

·        Convert Binary Search Tree into Binary Tree such that sum of all greater keys is added to every key and  Write a code in java to Convert Binary Search Tree drawn into Balanced Binary Search Tree·        

Answer 1

import java.util.*;


class Node {
	int data;
	Node left, right;


	public Node(int data) {
		this.data = data;
		left = right = null;
	}
}


class BinaryTree {
	Node root;


	void storeNodes(Node root, Vector<Node> nodes) {


		if (root == null)
			return;


		storeNodes(root.left, nodes);
		nodes.add(root);
		storeNodes(root.right, nodes);
	}


	Node buildTree(Vector<Node> nodes, int start, int end) {


		if (start > end)
			return null;


		int mid = (start + end) / 2;
		Node node = nodes.get(mid);


		node.left = buildTree(nodes, start, mid - 1);
		node.right = buildTree(nodes, mid + 1, end);


		return node;
	}


	Node buildTree(Node root) {


		Vector<Node> nodes = new Vector<Node>();
		storeNodes(root, nodes);


		int n = nodes.size();
		return buildTree(nodes, 0, n - 1);
	}


	void preOrder(Node node) {
		if (node == null)
			return;
		System.out.print(node.data + " ");
		preOrder(node.left);
		preOrder(node.right);
	}


	public static void main(String[] args) {
		/*
		 * Constructed skewed binary tree is 
		 *         15 
		 *         /
		 *        20
		 *        /
		 *       70
		 *      /
		 *     10
		 *     /
		 *    90
		*/
		BinaryTree tree = new BinaryTree();
		tree.root = new Node(15);
		tree.root.left = new Node(20);
		tree.root.left.left = new Node(70);
		tree.root.left.left.left = new Node(10);
		tree.root.left.left.left.left = new Node(90);


		tree.root = tree.buildTree(tree.root);
		System.out.println("Preorder traversal of balanced BST is :");
		tree.preOrder(tree.root);
	}
}