What\'s the difference between linked list and binary tree? Solution Linked List

Question

Explanation / Answer

Linked List: Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7) Binary tree: Node(1) / Node(2) / / Node(3) RootNode(4) Node(5) / Node(6) Node(7) In a linked list, the items are linked together through a single next pointer. In a binary tree, each node can have 0, 1 or 2 subnodes, where (in case of a binary search tree) the key of the left node is lesser than the key of the node and the key of the right node is more than the node. As long as the tree is balanced, the searchpath to each item is a lot shorter than that in a linked list. Searchpaths: ------ ------ ------ key List Tree ------ ------ ------ 1 1 3 2 2 2 3 3 3 4 4 1 5 5 3 6 6 2 7 7 3 ------ ------ ------ avg 4 2.43 ------ ------ ------ By larger structures the average search path becomes significant smaller: ------ ------ ------ items List Tree ------ ------ ------ 1 1 1 3 2 1.67 7 4 2.43 15 8 3.29 31 16 4.16 63 32 5.09 ------ ------ ------

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.