Binary Search Tree: Difference between revisions
Jump to navigation
Jump to search
Created page with "A Binary Search Tree is a binary tree with a specific ordering property: for any sub-tree, the left nodes is less that the root node and the right nodes is bigger to the root..." |
No edit summary |
||
| Line 7: | Line 7: | ||
'''Find''' and '''insert''' operations in a '''unbalanced''' Search Tree is '''O(n)''' whereas it is '''O(log n)''' in a '''balanced''' tree. | '''Find''' and '''insert''' operations in a '''unbalanced''' Search Tree is '''O(n)''' whereas it is '''O(log n)''' in a '''balanced''' tree. | ||
There are | There are 4 ways to traverse a binary tree: | ||
* In-order: left node, root node, the then right node | * In-order: left node, root node, the then right node | ||
* Pre-order: the root, the left node, then the right node | * Pre-order: the root, the left node, then the right node | ||
* Post-order: the left node, the right node, then the root node | * Post-order: the left node, the right node, then the root node | ||
* Level-order: BFS traversal | |||
In order in Binary Search Tree, the in-order traversal is preferred. | In order in Binary Search Tree, the in-order traversal is preferred. | ||
Revision as of 06:50, 3 June 2018
A Binary Search Tree is a binary tree with a specific ordering property: for any sub-tree, the left nodes is less that the root node and the right nodes is bigger to the root node.
Searching in a Binary Search Tree is really fast thanks to its ordering property.
Insertion in a Binary Search Tree can unbalance the tree.
Find and insert operations in a unbalanced Search Tree is O(n) whereas it is O(log n) in a balanced tree.
There are 4 ways to traverse a binary tree:
- In-order: left node, root node, the then right node
- Pre-order: the root, the left node, then the right node
- Post-order: the left node, the right node, then the root node
- Level-order: BFS traversal
In order in Binary Search Tree, the in-order traversal is preferred.