Binary Trees – Linked Lists

Binary trees are useful data structures used to solve specific computational problems. They provide a visual representation of how data can be stored and linked.

Computers use linked lists to store the information of binary trees. This blog post will look at how we can convert a binary tree into a linked list.

Binary Tree #1


binary-search-tree-01

Linked List



Memory Address binary-tree-nodeNode Value binary-tree-left-pointerLeft Pointer binary-tree-right-pointerRight Pointer
0 K 4 1
1 T 2 3
2 S 5
3 U
4 A
5 L
6
7

The Tree is accessed using two pointers:

  • RootPointer = 0
  • EndPointer = 6

Each time a new element is added to the tree, the EndPointer increments by 1.

Binary Tree #2


binary-search-tree-02

Linked List



Memory Address binary-tree-nodeNode Value binary-tree-left-pointerLeft Pointer binary-tree-right-pointerRight Pointer
0 T
1 F
2 L
3 B
4 A
5 U
6 C

Complete the linked list above.

What would happen if the next value to be added to the tree was letter S?

Binary Tree #3


The values have been received/stored in the following order:
N,E,T,F,B,V,U,C,Y

Draw the binary search tree on paper and complete the following link list table:

Memory Address binary-tree-nodeNode Value binary-tree-left-pointerLeft Pointer binary-tree-right-pointerRight Pointer

What would happen if the next value to be added to the tree was letter K?

Share Button
Posted in Computer Science, Computing Concepts Tagged with:

Our Latest Book