Skip to content

tree.md

Latest commit

 

History

History
231 lines (159 loc) · 9.39 KB

tree.md

File metadata and controls

231 lines (159 loc) · 9.39 KB
Raw

Tree

  1. Tree
  2. Tree Traversal
  3. Binary Search Tree
  4. Binary Search Tree Traversal

Tree

Description

Tree data structure is a hierarchical structure used to represent and organise data in the form of parent-child relationship.

The topmost node of a tree is call root and the nodes below it are called child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure.

Visually, the tree structure looks like this:

         5
       / | \
      7  9  2
     / \ |  /\
    3  4 0 8  6

Implement a class to represent a tree node and its relevant methods:

  • add(value) Add a child node
  • remove(value) Remove a child node, which has the given value

Implementation

Back to index

Tree Traversal

Description

There are two ways to traverse a tree: Depth First Search (DFS) and Breadth First Search(BFS)

To traverse a tree with DFS: We first completely traverse the left subtree and then move to the right subtree.

To traverse a tree with BFS: We traverse all the nodes present in the same level completely and then traverse the next level.

Example

         5
       / | \
      7  9  2
     / \ |  /\
    3  4 0 8  6

DFS:

  1. treeArr = [Node(5)]
  2. Shift (Remove the first element) treeArr to get 5 - [5] and unshift the children of Node(5), put the children to the top of array - treeArr = [Node(7), Node(9), Node(2)]
  3. Shift treeArr to get 7 - [5, 7] and unshift the children of Node(7) - treeArr = [ Node(3), Node(4), Node(9), Node(2)]
  4. Shift treeArr to get 3 - [5, 7, 3] and unshift the children of Node(3) (no children) - treeArr = [ Node(4), Node(9), Node(2)]
  5. Shift treeArr to get 4 - [5, 7, 3, 4] and unshift the children of Node(4) (no children) - treeArr = [Node(9), Node(2)]
  6. Shift treeArr to get 9 - [5, 7, 3, 4, 9] and unshift the children of Node(9) - treeArr = [Node(0), Node(2)]
  7. Shift treeArr to get 0 - [5, 7, 3, 4, 9, 0] and unshift the children of Node(0) (no children) - treeArr = [ Node(2)]

Up to now, you can get the idea that DFS is actually a stack operation: in every loop, you read the first element of treeArr and put its children on the top of the array until all nodes in treeArr are read.

BFS:

  1. treeArr = [Node(5)]
  2. Shift (Remove the first element) treeArr to get 5 - [5] and push the children of Node(5), put the children to the end of array - treeArr = [Node(7), Node(9), Node(2)]
  3. Shift treeArr to get 7 - [5, 7] and push the children of Node(7) - treeArr = [Node(9), Node(2), Node(3), Node(4)]
  4. Shift treeArr to get 9 - [5, 7, 9] and push the children of Node(9)- treeArr = [Node(2), Node(3), Node(4), Node(0)]
  5. Shift treeArr to get 2 - [5, 7, 9, 2] and push the children of Node(2)- treeArr = [Node(3), Node(4), Node(0), Node(8), Node(6)]
  6. Shift treeArr to get 3 - [5, 7, 9, 2, 3] and push the children of Node(3) (no children) - treeArr = [Node(4), Node(0), Node(8), Node(6)]
  7. Shift treeArr to get 4 - [5, 7, 9, 2, 3, 4] and push the children of Node(4) (no children) - treeArr = [Node(0), Node(8), Node(6)]

From above, BFS is actually a queue opeartion, in every loop, you read the first element of treeArr and push its children to the end of the array until all nodes in treeArr are read.

Implementation

Back to index

Binary Search Tree

Description

Binary Search Tree is a tree data structure with the properties:

  1. Each node has at most two children (left, right).
  2. All the nodes of a node's left subtree are smaller than the node.
  3. All the nodes of a node's right sub-tree are larger than the node.
  4. There must be no duplicated nodes.

Implement a Binary Search Tree data structure and its relevant methods:

  • insert(data) Add a node to BST.
  • contain(data) Check if the node with the given value exists in BST.
  • delete(data) Delete a node with the given value.
  • min() Find the minimum value in BST
  • max() Find the maximum value in BST

Solution

             10
             / \
            5   15
           /    / \
          2    12 20

Insertion: In the above BST, insert 3:

  1. Initialize the current node with root node: currentNode = 10
  2. Compare 3 with the current node. If smaller then move left (currentNode = currentNode.left); if bigger, then move right(currentNode = currentNode.right).
  3. Repeat until you reach the leaf node. So in this example: 3 < 10, move left, which is 5. Compare with 5: 3 < 5, move left, which is 2. Compare with 2, 3 > 2, move right. Because we've reached to the leaf, so put 3 as the child of Node 2.
  4. After insertion, the tree is like this:
             10
             / \
            5   15
           /    / \
          2    12 20
           \
            3

Searching: Search to find out if the tree contains Node with value of 12.

The operation is very similar to insertion, start from the root, if the value to search is smaller, move left; if bigger, move right.

In this example, we first compare root node(10) with the node to search(12). Because 12 > 10, move right, which is 15. Since 12 < 15, move right, which is exactly 12 - The node we are going to find!

Deletion: Deletion is a bit tricky. The basic approach is to find out the node to delete and then remove it. We need currentNode to store the node itself and parentNode as the parent node of currentNode, which is useful in "deleting" node. Based on the position of the currentNode, it has three cases:

  1. Node to delete is a leaf node. This is the easiest case: just assign the node as null.

    Delete Node(12) (leaf node): Find out currentNode = Node(12) and parentNode = Node(15) Because Node(12)is a leaf node(!currentNode.left && !currentNode.right). Set the currentNode as null. We do it via parentNode. Find out if currentNode is parentNode left or right child and set parentNode.left or parentNode.right as null.

  2. Node to delete has one child. It's also simple,: just replace the node with its child.

    Delete Node(5) (has one child): Find out currentNode = Node(5) and parentNode = Node(10). Because Node(5) has only one child. So just point parentNode.left or parentNode.right (depending on current node is parent node's left or right child.) to its only child (currentNode.left || currentNode.right). After deletion, the tree looks like this:

              10
          / \
         2   15
             / \
            12 20

  3. Node to delete has two children. This case is the most complex, which involves the re-arrangement of the BST. To achieve that, find out its inorder successor, which is exactly the minimum value from its right subtree and move the inorder successor to the position of the node to delete. For example, we are going to delete Node 10 (root node). The inorder successor of Node(10) is Node(12), which is the minimum node in its right subtree. Now move Node12 to Node10 to complete the deletion. After it, the tree looks like this:

              12
          / \
         5   15
        /     \
       2       20

min: Based on the property of BST, keep moving left until it reaches the left most leaf.

max: Based on the property of BST, keep moving right until it reaches the right most leaf.

Implementation

Back to index

Binary Search Tree Traversal

Description

There are three ways to traverse a binary search tree:

  1. Inorder: At first traverse left subtree then visit the root and then traverse the right subtree.(Left - Root - Right) Inorder traversal gives the values of the nodes in sorted order.

  2. Preorder: At first visit the root, then traverse left subtree and then traverse right subtree.(Root - Left - Right)

  3. Postorder: At first traverse left subtree, then traverse right subtree and then visit root.(Left - Right - Root)

Example


              10
             /  \
            5   15
           / \  / \
          2  6 12 20
         / \      / \
        1   3    18 30
  • Inorder traversal: [1, 2, 3, 5, 6, 10, 12, 15, 18, 20, 30]
  • Preorder traversal: [10, 5, 2, 1, 3, 6, 15, 12, 20, 18, 30]
  • Postorder traversal: [1, 3, 2, 6, 5, 12, 18, 30, 20, 15, 10]

Implementation

Back to index