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/.
ProblemGiven 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