Trees

Some Important Notes We Need to Know about Trees…

Anny's Blog
Nov 1 · 5 min read
From Javatpoint.com

✥ What is Tree in Data Structure:

From gatevidyalay.com

Think of Tree data structure just like a tree. Body (Node A) is the parent, branches (Node B & Node C) are the children, and leaves (Leaf nodes) are grandchildren.

Within a tree, there are also subtrees (two red circles). Subtrees are big branches (B & C nodes) that have children and grandchildren (leaves).

From en.wikipedia.org

What is Binary Tree?

Binary Tree is a tree that each node has only one or at most two children, which are referred to as left node child and right node child.


☛ Perfect Binary Tree:

● Every node in this tree can have zero children or two children, and all leaves are on the same level.

● The number of total nodes on each level double as we move down the tree.

● The number of total nodes on the last level is equal to the sum of number of nodes on all levels Plus one (Pic above: 4 = 3 + 1). Total number of all nodes on this tree is 2^h minute 1 where h is number of levels(or steps). For example in picture above, h is 3 (3 steps) → total nodes (7)= 2³ — 1.

● Time Complexity is O(log n), where log = h.

☛ Full Binary Tree:

● Every node in this tree other than the leaves have two children.


Binary Search Tree:

  • Binary Search Tree (BST) is a sorted binary tree.
  • All child nodes on the right must be greater than the parent node. For example: 36 > 25; 22 > 20; etc…Just remember: Left side: decrease; right side: increase.
  • A node can only has up to two children because it’s binary tree.

Pros 👍 :

  • Time Complexity in all operations is O(log n) if it’s not an unbalance BST, which is better than O(n). Unbalance BST (similar to Linked List) cost O(n) operation.
  • Nodes are sorted (in order)-> lookup (O(log n)) which is faster than lookup in an Array. For insert or delete operation, if we do it in somewhere other than the end of an array, all indexes in that array will be shifted.
  • BST is better than hash table that all nodes in BST are sorted (in order) and they are structured (parent-child), whereas elements in Hash table are not structured and not in order.
  • Flexible size (nodes can be added anywhere in BST, and we can keep growing our tree)

Cons 👎 :

  • There is no constant time operation (no O(1)).

Binary Heap:

Max Heap & Min Heap:

From studytonight.com

Lookup Operation — O(n): in Binary Heap(BH), nodes are not in order like in BST. We can’t look left and right like in BST. In BH, we don’t know if left value is greater or less than the right value, so to lookup an item we basically have to check every single node in the BH. Therefore, lookup take O(n) in time complexity.

Even though lookup operation in BH take O(n) time which is similar to lookup in an Array or in a Linked List, look up in BH is still better than in Array or Linked List. The reason is because BH is sorted by levels (Max Heap, or Min Heap), so we don’t need to look at all levels.

Insert Operation or Delete Operation: O(log n).

Special Note: we can implemented BH using Array. BH is good for Priority Queues, which means an element with a higher priority is serve before an element with a lower priority. For example, we can think of priority as getting line for getting on an airplane. First class people who paid more money get to get in first, before economic class people.

Binary Heap Pros & Cons:

Pros 👍 :

  • Better than O(n)
  • Priority (good in prior queues in example above)
  • Flexible size
  • Fast insertion (sorted by levels)

Cons 👎 :

  • Slow look up (slower than BST)

Trie:

From slideshare.net
  • To find a word in a trie, we just need to know the length of the word, and Big O is also equal to O(length of the word). → fast lookup which is an advantage in time complexity.
  • Trie also has an advantage in space complexity because we use prefixes in trie. If there are two words that has the same letter, we just need to have one node for that same letter and distribute two words from that one letter. For example, the letter a in picture above is for two words (aeef and ad).

Thank you for reading! 😊

Anny's Blog

Written by

“Knowledge is love and light and vision.” I love knowledge, and I love sharing what I love to the community.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade