package deneme01;
import lombok.NoArgsConstructor;
import java.util.*;
class Node {
public Node parent;
int data, depth, weight;
Node left, right;
int height;
boolean ignore;
public Node(int data) {
this.data = data;
}
public boolean isLeaf() {
if (left == null && right == null)
return true;
else return false;
}
@Override
public String toString() {
return "" + data;
}
}
@NoArgsConstructor
class Tree {
Node root;
public Tree(Node root) {
this.root = root;
}
public void preOrderRecursive(Node node) {
if (node == null) {
return;
}
System.out.print (" " + node.data);
preOrderRecursive (node.left);
preOrderRecursive (node.right);
}
public void inOrderRecursive(Node node) {
if (node == null) {
return;
}
preOrderRecursive (node.left);
System.out.print (" " + node.data);
preOrderRecursive (node.right);
}
public void postOrderRecursive(Node node) {
if (node == null) {
return;
}
preOrderRecursive (node.left);
preOrderRecursive (node.right);
System.out.print (" " + node.data);
}
public void preOrderIterative() {
Stack<Node> stack = new Stack<> ();
stack.push (root);
while (!stack.isEmpty ()) {
Node pop = stack.pop ();
System.out.print (" " + pop.data);
if (pop.right != null) stack.push (pop.right);
if (pop.left != null) stack.push (pop.left);
}
}
public void inOrderIterative() {
Stack<Node> stack = new Stack<> ();
Node current = root;
while (!stack.isEmpty () || null != current) {
if (current != null) {
stack.push (current);
current = current.left;
} else {
Node pop = stack.pop ();
System.out.print (" " + pop.data);
current = pop.right;
}
}
}
public void postOrderIterative() {
Stack<Node> stack = new Stack<> ();
stack.push (root);
while (!stack.isEmpty ()) {
Node peek = stack.peek ();
if (peek.isLeaf ()) {
Node pop = stack.pop ();
System.out.print (" " + pop.data);
} else {
if (peek.right != null) {
stack.push (peek.right);
peek.right = null;
}
if (peek.left != null) {
stack.push (peek.left);
peek.left = null;
}
}
}
}
public void bfsRecursive() {
int height = Math.max (height (root.left), height (root.right)) + 1;
for (int i = 1; i <= height; i++) {
bfs (root, i);
System.out.println ("");
}
}
private void bfs(Node node, int height) {
if (node == null) {
return;
}
if (height == 1) {
System.out.print (" " + node.data);
} else if (height > 1) {
bfs (node.left, height - 1);
bfs (node.right, height - 1);
}
}
public void bfsIterative() {
Queue<Node> queue = new LinkedList<> ();
root.depth = 0;
queue.add (root);
int currentDepth = root.depth;
while (!queue.isEmpty ()) {
Node poll = queue.poll ();
if (currentDepth != poll.depth) {
System.out.println ("");
currentDepth = poll.depth;
}
System.out.print (" " + poll.data);
if (poll.left != null) {
poll.left.depth = poll.depth + 1;
queue.add (poll.left);
}
if (poll.right != null) {
poll.right.depth = poll.depth + 1;
queue.add (poll.right);
}
}
}
public void bfsIterativeBottom2Top() {
Queue<Node> queue = new LinkedList<> ();
Stack<Node> stack = new Stack<> ();
queue.add (root);
while (!queue.isEmpty ()) {
Node poll = queue.poll ();
//System.out.print(" " + poll.data);
stack.push (poll);
if (poll.right != null) {
queue.add (poll.right);
}
if (poll.left != null) {
queue.add (poll.left);
}
}
while (!stack.isEmpty ()) {
Node pop = stack.pop ();
System.out.print (" " + pop.data);
}
}
public int size() {
Stack<Node> stack = new Stack<> ();
stack.push (root);
int size = 0;
while (!stack.isEmpty ()) {
Node pop = stack.pop ();
size++;
if (pop.right != null) {
stack.push (pop.right);
}
if (pop.left != null) {
stack.push (pop.left);
}
}
return size;
}
public int height() {
return height (root);
}
private int height(Node node) {
if (node == null) {
return 0;
}
return Math.max (height (node.left), height (node.right)) + 1;
}
public Node insert(int x) {
return insert (x, root);
}
public Node insert(int x, Node node) {
if (node == null) {
node = new Node (x);
}
if (x < node.data) {
node = insert (x, node);
if (x < node.left.data) {
node = rightRotate (node);
} else {
node = doubleRightRotate (node);
}
} else if (x > node.data) {
node = insert (x, node);
if (x > node.right.data) {
node = leftRotate (node);
} else {
node = doubleLeftRotate (node);
}
} else {
//duplicate , ignore
}
return node;
}
private Node doubleRightRotate(Node node) {
node.left = leftRotate (node.left);
return rightRotate (node);
}
private Node rightRotate(Node k1) {
Node k2 = k1.left;
k1.left = k2.right;
k2.right = k1;
k1.height = Math.max (height (k1.left), height (k1.left)) + 1;
k2.height = Math.max (height (k2.left), height (k2.left)) + 1;
return k2;
}
private Node doubleLeftRotate(Node node) {
node.right = rightRotate (node.right);
return leftRotate (node);
}
private Node leftRotate(Node k1) {
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max (height (k1.left), height (k1.left)) + 1;
k2.height = Math.max (height (k2.left), height (k2.left)) + 1;
return k2;
}
public void findMaxDepth() {
Stack<Node> nodes = new Stack<> ();
root.depth = 0;
nodes.push (root);
int maxDepth = 0;
while (!nodes.isEmpty ()) {
Node current = nodes.pop ();
System.out.printf ("%s ", current.data);
if (maxDepth < current.depth) {
maxDepth = current.depth;
}
if (current.right != null) {
current.right.depth = current.depth + 1;
nodes.push (current.right);
}
if (current.left != null) {
current.left.depth = current.depth + 1;
nodes.push (current.left);
}
}
System.out.println ("maxDepth = " + maxDepth);
}
//shortest path = breadth first search
public void findMinDepth() {
Queue<Node> queue = new LinkedList<> ();
root.depth = 0;
queue.add (root);
int minDepth = Integer.MAX_VALUE;
while (!queue.isEmpty ()) {
Node poll = queue.poll ();
if (poll.isLeaf () && minDepth > poll.depth) {
minDepth = poll.depth;
}
System.out.print (" " + poll.data);
if (poll.left != null) {
poll.left.depth = poll.depth + 1;
queue.add (poll.left);
}
if (poll.right != null) {
poll.right.depth = poll.depth + 1;
queue.add (poll.right);
}
}
System.out.println ("minDepth = " + minDepth);
}
//fix this!!!
public void traverseAndCalculateNodeTotalWeightTop2Bottom() {
Stack<Node> stack = new Stack<> ();
root.weight = root.data;
stack.push (root);
while (!stack.isEmpty ()) {
Node peek = stack.peek ();
if (peek.isLeaf ()) {
Node pop = stack.pop ();
System.out.print ("[ " + pop.data + " nw:" + pop.weight + "] ");
} else {
if (peek.right != null) {
peek.right.weight = peek.weight + peek.right.data;
stack.push (peek.right);
peek.right = null;
}
if (peek.left != null) {
peek.left.weight = peek.weight + peek.left.data;
stack.push (peek.left);
peek.left = null;
}
}
}
}
public int[] averageInEachLevel() {
int[] averages = new int[height (root)];
Queue<Node> queue = new LinkedList<> ();
queue.add (root);
int currentDepth = 0;
root.depth = 0;
int levelSum = 0, levelMember = 0;
while (!queue.isEmpty ()) {
Node poll = queue.poll ();
if (currentDepth != poll.depth) {
System.out.print (" => sum: " + levelSum + " member: " + levelMember);
averages[poll.depth - 1] = levelSum / levelMember;
levelMember = 0;
levelSum = 0;
System.out.println (" ");
currentDepth = poll.depth;
}
levelSum += poll.data;
levelMember++;
System.out.print (" " + poll.data);
if (poll.left != null) {
poll.left.depth = poll.depth + 1;
queue.add (poll.left);
}
if (poll.right != null) {
poll.right.depth = poll.depth + 1;
queue.add (poll.right);
}
}
averages[averages.length - 1] = levelSum / levelMember;
return averages;
}
public Double[] averageInEachLevel2() {
ArrayList<Double> averages = new ArrayList<> ();
Queue<Node> queue = new LinkedList<> ();
queue.add (root);
List<List<Node>> levelMembers = new ArrayList<> ();
ArrayList<Node> rootLevel = new ArrayList<> ();
rootLevel.add (root);
levelMembers.add (rootLevel);
while (!queue.isEmpty ()) {
double count = queue.size ();
double sum = 0;
ArrayList currentLevel = new ArrayList<> ();
for (int i = 0; i < count; i++) {
Node poll = queue.poll ();
sum += poll.data;
if (poll.right != null) {
queue.add (poll.right);
currentLevel.add (poll.right);
}
if (poll.left != null) {
queue.add (poll.left);
currentLevel.add (poll.left);
}
}
averages.add (sum / count);
levelMembers.add (currentLevel);
}
return averages.toArray (new Double[averages.size ()]);
}
//----
public boolean find(int id) {
Node current = root;
while (current != null) {
if (current.data == id) {
return true;
} else if (current.data > id) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
//while deleting you need two things ! parent and isLeftChild !
//for the rest of the scenarios you need to go through to following considerations
//is it root ? is it leftChild ? is it right child ?
//Scenarios are is leaf node ? has only one right child ? has only one left child ? has two child ?
public boolean deleteUnbalanced(int id) {
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while (current.data != id) {
parent = current;
if (current.data > id) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
if (current == null) {
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if (current.left == null && current.right == null) {
if (current == root) {
root = null;
}
if (isLeftChild == true) {
parent.left = null;
} else {
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if (current.right == null) {
if (current == root) {
root = current.left;
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
} else if (current.left == null) {
if (current == root) {
root = current.right;
} else if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
} else if (current.left != null && current.right != null) {
//now we have found the minimum element in the right sub tree
Node successor = getSuccessor (current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
//from right to leftmost...
public Node getSuccessor(Node deleleNode) {
Node successsor = null;
Node successsorParent = null;
Node current = deleleNode.right;
while (current != null) {
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
//if it does have the right child, add it to the left of successorParent.
//successsorParent
if (successsor != deleleNode.right) {
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public boolean delete(int x) {
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while (current.data != x) {
parent = current;
if (current.data < x) {
isLeftChild = false;
current = current.right;
} else {
isLeftChild = true;
current = current.left;
}
if (current == null) {
return false;// not found the X in the tree
}
}
if (current.left == null && current.right == null) {
if (current == root) {
root = null;
}
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
} else if (current.right != null) {
if (current == root) {
root = current.right;
}
if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
} else if (current.left != null) {
if (current == root) {
root = current.left;
}
if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
} else if (current.left != null && current.right != null) {
Node successor = getSuccessor (current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
current.left = successor;
} else {
current.right = successor;
}
successor.left = current.left;
}
return isLeftChild;
}
public void insertUnBalanced(int id) {
Node newNode = new Node (id);
if (root == null) {
root = newNode;
return;
}
Node current = root;
Node parent = null;
while (true) {
parent = current;
if (id < current.data) {
current = current.left;
if (current == null) {
parent.left = newNode;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
//---------
public void allPathsToLeafNodesWithPreOrderDFS() {
Stack<Node> stack = new Stack<> ();
stack.push (root);
List<Deque<Integer>> paths = new ArrayList<> ();
while (!stack.isEmpty ()) {
Node pop = stack.pop ();
System.out.print (" " + pop.data);
if (pop.isLeaf ()) {
Deque<Integer> path = new ArrayDeque<> ();
Node current = pop;
while (current != null) {
path.add (current.data);
current = current.parent;
}
paths.add (path);
}
if (pop.right != null) {
pop.right.parent = pop;
stack.push (pop.right);
}
if (pop.left != null) {
pop.left.parent = pop;
stack.push (pop.left);
}
}
System.out.println ("paths = " + paths);
}
public void allPathsToLeafNodesWithInOrderDFS() {
Stack<Node> stack = new Stack<> ();
List<Deque<Integer>> paths = new ArrayList<> ();
Node current = root;
while (!stack.isEmpty () || current != null) {
if (current != null) {
stack.push (current);
if (current.left != null) current.left.parent = current;
current = current.left;
} else {
Node pop = stack.pop ();
System.out.println (" " + pop.data);
if (pop.isLeaf ()) {
Deque<Integer> path = new ArrayDeque<> ();
Node now = pop;
while (now != null) {
path.add (now.data);
now = now.parent;
}
paths.add (path);
}
current = pop.right;
if (pop.right != null) pop.right.parent = pop;
}
}
System.out.println ("paths = " + paths);
}
public void allPathsToLeafNodesWithBFS() {
List<Deque<Integer>> paths = new ArrayList<> ();
Queue<Node> queue = new LinkedList<> ();
queue.add (root);
while (!queue.isEmpty ()) {
Node poll = queue.poll ();
System.out.println ("poll = " + poll);
if (poll.isLeaf ()) {
Deque<Integer> path = new ArrayDeque<> ();
Node current = poll;
while (current != null) {
path.add (current.data);
current = current.parent;
}
paths.add (path);
}
if (poll.left != null) {
poll.left.parent = poll;
queue.add (poll.left);
}
if (poll.right != null) {
poll.right.parent = poll;
queue.add (poll.right);
}
}
System.out.println ("paths = " + paths);
}
}
public class Main {
// 40
// 20 50
// 10 30 45 60
// 5 15 25 35 44 46 55 61
//4 6 14 16 24 26 34 36 43 47 54 56 62
// 63
// 64
// 40 20 10 5 15 30 25 35 50 45 44 46 60 55 61
// 5 10 15 20 25 30 35 40 44 45 46 50 55 60 61
// 5 15 10 25 35 30 20 44 46 45 55 61 60 50 40
public static String traversePreOrder(Node root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder ();
sb.append (root.data);
String pointerRight = "└──";
String pointerLeft = (root.right != null) ? "├──" : "└──";
traverseNodes (sb, "", pointerLeft, root.left, root.right != null);
traverseNodes (sb, "", pointerRight, root.right, false);
return sb.toString ();
}
public static void traverseNodes(StringBuilder sb, String padding, String pointer, Node node, boolean hasRightSibling) {
if (node != null) {
sb.append ("\n");
sb.append (padding);
sb.append (pointer);
sb.append (node.data);
StringBuilder paddingBuilder = new StringBuilder (padding);
if (hasRightSibling) {
paddingBuilder.append ("│ ");
} else {
paddingBuilder.append (" ");
}
String paddingForBoth = paddingBuilder.toString ();
String pointerRight = "└──";
String pointerLeft = (node.right != null) ? "├──" : "└──";
traverseNodes (sb, paddingForBoth, pointerLeft, node.left, node.right != null);
traverseNodes (sb, paddingForBoth, pointerRight, node.right, false);
}
}
public static void main(String[] args) {
Tree tree = buildTree ();
System.out.println ("Before deletion --");
String s = traversePreOrder (tree.root);
System.out.println (s);
tree.deleteUnbalanced (40);
System.out.println ("After insertion --");
s = traversePreOrder (tree.root);
System.out.println (s);
System.out.println ("");
tree = buildTree ();
System.out.println ("Before insertion --");
s = traversePreOrder (tree.root);
System.out.println (s);
tree.insertUnBalanced (12);
System.out.println ("After insertion --");
s = traversePreOrder (tree.root);
System.out.println (s);
System.out.println ("");
tree = buildTree ();
System.out.println ("PreOrder --");
tree.preOrderIterative ();
System.out.println ("");
tree = buildTree ();
System.out.println ("InOrder --");
tree.inOrderIterative ();
System.out.println ("");
tree = buildTree ();
System.out.println ("PostOrder --");
tree.postOrderIterative ();
System.out.println ("");
System.out.println ("");
tree = buildTree ();
System.out.println (" Size : " + tree.size ());
System.out.println ("");
System.out.println ("-- tree height--");
tree = buildTree ();
System.out.println (" Height : " + tree.height ());
System.out.println ("");
System.out.println ("-- bfs recursive--");
tree = buildTree ();
tree.bfsRecursive ();
System.out.println ("");
System.out.println ("-- bfs iterative --");
tree = buildTree ();
tree.bfsIterative ();
System.out.println ("");
System.out.println ("-- each level average iterative --");
tree = buildTree ();
tree.averageInEachLevel ();
System.out.println ("");
System.out.println ("-- each level average iterative 2 --");
tree = buildTree ();
tree.averageInEachLevel2 ();
System.out.println ("");
System.out.println ("-- maxDepth --");
tree = buildTree ();
System.out.println ("");
tree.findMaxDepth ();
System.out.println ("");
System.out.println ("-- totalNodeWeights --");
tree = buildTree ();
System.out.println ("");
tree.traverseAndCalculateNodeTotalWeightTop2Bottom ();
System.out.println ("");
System.out.println ("-- findMinDepthToLeafNode --");
tree = buildTree ();
System.out.println ("");
tree.findMinDepth ();
System.out.println ("");
System.out.println ("-- findMinDepthToLeafNode --");
tree = buildTree ();
System.out.println ("");
tree.bfsIterativeBottom2Top ();
System.out.println ("");
System.out.println ("-- allPaths2LeafNodesWithPreOrderDFS --");
tree = buildTree ();
System.out.println ("");
tree.allPathsToLeafNodesWithPreOrderDFS ();
System.out.println ("");
System.out.println ("-- allPaths2LeafNodesWithInOrderDFS --");
tree = buildTree ();
System.out.println ("");
tree.allPathsToLeafNodesWithInOrderDFS ();
System.out.println ("");
}
// 40
// 20 50
// 10 30 45 60
// 15 25 35 55 61
// 14 16 24 26 34 36 54 56 62
// 63
// 64
private static Tree buildTree() {
Tree tree = new Tree ();
Node root = new Node (400);
tree.root = root;
tree.root.left = new Node (200);
tree.root.right = new Node (500);
tree.root.left.left = new Node (100);
tree.root.left.right = new Node (300);
tree.root.right.left = new Node (450);
tree.root.right.right = new Node (600);
tree.root.left.left.left = new Node (50);
tree.root.left.left.right = new Node (150);
tree.root.left.right.left = new Node (250);
tree.root.left.right.right = new Node (350);
tree.root.right.left.left = new Node (440);
tree.root.right.left.right = new Node (460);
tree.root.right.right.left = new Node (550);
tree.root.right.right.right = new Node (610);
tree.root.right.right.left.left = new Node (540);
tree.root.right.right.left.right = new Node (560);
tree.root.left.left.left.left = new Node (40);
tree.root.left.left.left.right = new Node (60);
tree.root.left.left.left.left.left = new Node (35);
tree.root.left.left.left.left.right = new Node (45);
tree.root.left.left.left.left.right.left = new Node (44);
tree.root.left.left.left.left.right.right = new Node (48);
tree.root.left.left.left.left.right.right.left = new Node (47);
tree.root.left.left.left.left.right.right.right = new Node (49);
tree.root.left.left.left.left.right.left.left = new Node (43);
tree.root.left.left.right.left = new Node (140);
tree.root.left.left.right.right = new Node (160);
tree.root.left.right.left.left = new Node (240);
tree.root.left.right.left.right = new Node (260);
tree.root.left.right.right.left = new Node (340);
tree.root.left.right.right.right = new Node (360);
tree.root.right.left.left.left = new Node (430);
tree.root.right.left.right.right = new Node (470);
tree.root.right.right.right.right = new Node (620);
tree.root.right.right.right.right.right = new Node (630);
tree.root.right.right.right.right.right.right = new Node (640);
return tree;
}
}