5.1.14 – 5.1.17 – Trees

5.1.14 – Describe how trees operate logically

binary tree is a tree data structure where each node has up to two child nodes, creating the branches of the tree. … Parent nodes are nodes with children, while child nodes may include references to their parents.

5.1.15 – Define the terms: parent, left-child, right-child, subtree, root and leaf

The topmost node is called root of the tree.

The elements that are directly under an element are called its children.

The element directly above something is called its parent.

For example, a is a child of f and f is the parent of a.

Elements with no children are called leaves.

Subtree’s

Subtree is defined as “The tree which is a child of a node. Note: The name emphasizes that everything which is a descendant of a tree node is a tree, too, and is a subset of the larger tree.”

Binary Tree

Binary tree is the tree in which every node has no, one or utmost two children.

There is no condition or relationship between the values of the parent and children nodes.

Binary Search Tree

In a binary search tree (which also inherits the properties of a binary tree), the node with value smaller than the parent node must become the left child and the node with value greater than or equal to the parent node must become the right child.

Another thing to note is that you cannot have duplicate values in a Binary Search Tree

5.1.16 – State the result of inorder, postorder and preorder tree traversal

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways.

Following are the generally used ways for traversing trees.

Draw a line around the binary tree As you visit them and you pass where the traversal is (left bottom or right) write out the value in the node. See below

5.1.17 – Sketch binary trees

What would an ordered Binary Tree look like for :

12,49,-3,8,23,9

This Binary Tree Visualiser Software is great for learning these

Deleting Nodes From a Binary Search Tree

https://www.youtube.com/watch?v=gcULXE7ViZw

Example

To delete the Root Node (Finland)

Amended Binary Search Tree with root node deleted.