Diameter of a Tree is the number of nodes on the longest path between two leaves in the tree

Diameter of a Tree is the number of nodes on the longest path between two leaves in the tree

Consider a particular "node":- we have three cases
1. Longest Possible path includes node->left and not this node
2. Longest Possible path includes node->right and not his node
3. Longest Possible path includes this "node"

Thus, longest possible path should be maximum of these three: (node->left, node->right, 1+height(node->left) + height(node->right))

OutPut

H
D
B
A
H
D
B
diamater7

Java Code

import java.util.ArrayList;
import java.util.List;

public class longestPathInTree {
    // node class
    class node {
        node right;
        String val;
        node left;

        public String getVal() {
            return val;
        }

        public void setVal(String val) {
            this.val = val;
        }

        public node getRight() {
            return right;
        }

        public void setRight(node right) {
            this.right = right;
        }

        public node getLeft() {
            return left;
        }

        public void setLeft(node left) {
            this.left = left;
        }

        public node(String val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        longestPathInTree path = new longestPathInTree();
        path.find();
    }

    public void find() {
        node root = new node("A");
        node b = new node("B");
        node c = new node("C");
        node d = new node("D");
        node e = new node("E");
        node f = new node("F");
        node g = new node("G");
        node h = new node("H");
        node i = new node("I");
        node j = new node("J");
        node k = new node("K");
        node l = new node("L");
        node m = new node("M");
        node n = new node("N");
        root.setLeft(b);
        root.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);
        c.setRight(g);
        d.setLeft(h);
        d.setRight(i);
        e.setLeft(j);
        e.setRight(k);
        f.setRight(l);
        f.setLeft(m);
        g.setLeft(n);

        int diameter = 0;
        List<node> leftPath = findLongestPath(root.getLeft());
        diameter = diameter + leftPath.size();
        for (int z = leftPath.size() - 1; z >= 0; z--) {
            System.out.println(leftPath.get(z).getVal());
        }
        System.out.println(root.getVal());
        List<node> rightPath = findLongestPath(root.getRight());
        diameter += rightPath.size();
        for (int z = rightPath.size() - 1; z >= 0; z--) {
            System.out.println(leftPath.get(z).getVal());
        }
        System.out.println("diamater: " + ++diameter);

    }

    /**
     * if node does not have child node, then it will be child node else move
     * inside
     *
     * @param n
     * @return
     */
    private List<node> findLongestPath(node n) {
        List<node> stacks = new ArrayList<node>();
        node left = n.getLeft();
        node right = n.getRight();
        stacks.add(n);
        if (left == null && right == null) {
            return stacks;
        } else {
            List<node> sl = new ArrayList<longestPathInTree.node>();
            List<node> sr = new ArrayList<longestPathInTree.node>();
            if (left != null) {
                // Find longest path to left of node.
                sl = findLongestPath(left);
            }
            if (right != null) {
                // Find longest path to right of node.
                sr = findLongestPath(right);
            }
            if (sl.size() >= sr.size()) {
                for (node e : sl) {
                    stacks.add(e);
                }
            } else {
                for (node e : sr) {
                    stacks.add(e);
                }
            }
            return stacks;
        }
    }
}

Tower Of Hanoi

 



Towers of Hanoi 

The objective is to move the entire stack to any other rod, obeying these rules: 

• Only one disk can be moved at a time
• Each move consists of taking the upper disk from one rod, adding it onto another rod, on top of any disks that you may have already placed on that rod.
• But no disk can be placed on top of a smaller disk 

The recursive algorithm

• move n-1 disk from the starting pole to the pole which is neither start nor target (intermediate)
• move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole
• The n-1 disks are moved recursively 

Pseudo code:

• if ( nDisks == 1 )    return( "Do this move: fromPeg --> toPeg" ); 
• else 
• helpPeg = peg index that is not equal to fromPeg and toPeg; 
• sol1 = hanoi( nDisks-1, fromPeg, helpPeg );
• myStep = "Do this move: fromPeg --> toPeg"; 
• sol2 = hanoi( nDisks-1, helpPeg, toPeg );

How to use the solutions sol1 and sol2 to solve hanoi(nDisks, fromPeg, toPeg): 
 1. first making the moves in sol1
 2. then do myStep
 3. finally, do the moves in sol2

OUTPUT

Move 2 from 2 to 1
Move1from 3 to 1
Move 1 from 3 to 1
Move 3 from 2 to 3
Move1from 1 to 2
Move 1 from 1 to 2
Move 2 from 1 to 3
Move1from 2 to 3
Move 1 from 2 to 3

Java Code

/**
 * three poles and n disks which fit on the poles
 * All disks have different size
 * they are stacked on pole 1 in the orders of their size
 * The largest disk is on the bottom, the smallest is on the top.
 * The task is to move all disk from pole 1 to pole 3 under the following restrictions
 * Only one disk can be moved
 * A larger disk can not be placed on a smaller disk
 *
 * recursive algorithm works like the following: move n-1 disk from the starting pole
 * move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole
 *
 * n-1 disks are moved recursively
 *
 * @author ravi
 *
 */
public class TowerOfHanoi {
    /**
     * Pole are labeled 1, 2,3
     * Each disk is also labeled
     *
     * @param args
     */
    public static void main(String[] args) {
        move(4, 1, 3);
    }
    /**
     * For first (n-1) elemnet, end pole will be intermediate pole
     * And n element will be moved to last pole
     *
     * @param n
     * @param stratPole
     * @param endPole
     */
    static void move(int n, int stratPole, int endPole){
        if(n==0){
            return;
        }
        if(n==1){
            System.out.println("Move" + n + "from "+ stratPole +" to " + endPole);
        }       
        int intermediatePole = 6-endPole - stratPole;//3+2+1=6
        move(n-1, stratPole, intermediatePole);
        System.out.println("Move " + n + " from "+ stratPole +" to " + endPole);
        move(n-1, intermediatePole, endPole);
    }

}

Binary Tree Example In Java

OUTPUT

----Binary Tree Example--------
Binar Tree with Root Value: 25
--------------------------
inserted value to left of node11
inserted value to right of node14
inserted value to right of node55
inserted value to right of node93
inserted value to right of node93
inserted value to right of node44
inserted value to left of node44
-----------------------------
Traversing order
Traversed Order 11
Traversed Order 14
Traversed Order 25
Traversed Order 44
Traversed Order 55
Traversed Order 93
 

---------------------------------------------------------------

Code as
---------


/**
 * Binary Search Tree Left node will be less than parent node Right node will be
 * greater than parent node Each node has distinct key Information represented
 * by node is the object element Nodes are compared according to their keys than
 * any part of their associate records
 *
 * @author ravi
 *
 */
public class BinaryTreeExample {
    /**
     * Inside this class we have a static node class and have two static node
     * variable Node left, Node right and int value to store the respective node
     * value.
     */
    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * Inside the main method we instantiate Binary Tree that call run( ) method
     */
    public static void main(String[] args) {
        System.out.println("----Binary Tree Example--------");
        BinaryTreeExample bTree = new BinaryTreeExample();
        bTree.run();
    }

    /**
     * The run method ( ) create an instance of node class start with node value
     * of 25
     */
    public void run() {
        Node rootnode = new Node(25);
        System.out.println("Binar Tree with Root Value: " + rootnode.value);
        System.out.println("--------------------------");
        /**
         * Add leaf values to Tree
         *
         * Information represented by node is the object element
         */
        insert(rootnode, 11);
        insert(rootnode, 14);
        insert(rootnode, 55);
        insert(rootnode, 93);
        insert(rootnode, 44);
        System.out.println("-----------------------------");
        System.out.println("Traversing order");
        printInOrder(rootnode);
    }

    /**
     * The insert method accept a node and int as argument value
     *
     * 2-->3--->4 (left->parent->right)
     *
     * @param node
     * @param value
     */
    public void insert(Node node, int value) {
        // left value will always be less than parent
        if (value < node.value) {
            // if left node exist, move inside.
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("inserted value to left of node" + value);
                /**
                 * left node object will get value
                 *
                 * create Node object with value and assign it left node
                 */
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            System.out.println("inserted value to right of node" + value);
            // right node ill have greater value
            // if right node exist
            if (node.right != null) {
                insert(node.right, value);
            } else {
                node.right = new Node(value);
            }
        }

    }

    /**
     * The rootnode.value return you the value of the node
     *
     * @param node
     */
    public void printInOrder(Node node) {
        if (node != null) {
            printInOrder(node.left);
            System.out.println("Traversed Order " + node.value);
            printInOrder(node.right);
        }
    }

}