Monday, February 10, 2014

Create linked lists of all the nodes at each depth for a BST

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/create-linked-lists-of-all-the-nodes-at-each-depth-for-a-binary-tree/.
Problem
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)

Example
So a binary tree such as :
       (1)
      /   \
     /     \
   (2)     (3)
  /  \     / \
(4)  (5) (6) (7)

Will return linked lists:
(1) => NULL
(2) => (3) => NULL
(4) => (5) => (6) => (7) => NULL

Solution

Method 1 - Level order traversal
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.

public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList(
        BinaryTreeNode root) {
    int level = 0;
    ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>();
    LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();
    list.add(root);
    result.add(level, list);
    while (true) {
        list = new LinkedList<BinaryTreeNode>();
        for (int i = 0; i < result.get(level).size(); i++) {
            BinaryTreeNode n = result.get(level).get(i);
            if (n != null) {
                if (n.getLeft() != null)
                    list.add(n.getLeft());
                if (n.getRight() != null)
                    list.add(n.getRight());
            }
        }
        if (list.size() > 0) {
            result.add(level + 1, list);
        } else {
            break;
        }
        level++;
    }
    return result;
}

Thanks.

0 comments:

Post a Comment