BFS/DFS
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224
// level 0 : 2^0 = 1
// level 1 : 2^1 = 2
// level 2 : 2^2 = 4
// level 3 : 2^3 = 8
// # of nodes = 2^h -1
// log nodes = height
// log 100 = 2
//10^2 = 1
class Node {
dynamic left;
dynamic right;
dynamic value;
Node(value) {
this.left = null;
this.right = null;
this.value = value;
}
Map<String, dynamic> toMap(){
return {
"value": value,
"left": left?.toMap(),
"right": right?.toMap()
};
}
}
class BinarySearchTree {
dynamic root;
BinarySearchTree() {
this.root = null;
}
Map<String, dynamic> toMap(){
return root?.toMap() ?? {};
}
insert(value) {
Node newNode = new Node(value);
if(root == null){
// Node.value = value;
root = newNode;
}else{
dynamic tree = traverse(root, newNode.value);
if(value > tree.value){
// print(tree.toString());
tree.right = newNode;
}else{
// print(tree.toString());
tree.left = newNode;
}
}
}
lookup(value) {
dynamic node = this.root;
while(true){
if(value < node.value){
if(node.left == null){
return null;
}
node = node.left ;
}else if(value == node.value){
return node.value;
}else {
if(node.right == null){
return null;
}
node = node.right;
}
}
}
traverse(node, value) {
dynamic tree = node;
while(true){
if(value < tree.value){
if(tree.left == null) return tree;
tree = tree.left;
}else{
if(tree.right == null )return tree;
tree = node.right;
}
}
return tree;
}
// iterative
breathFirstSearch(){
var currentNode = root;
var list = [];
var queue = [];
queue.add(currentNode);
while(queue.length > 0){
print(currentNode.value);
currentNode = queue.removeAt(0); //when you remove from queue here the queue becomes empty again at initial stage
list.add(currentNode.value);
if(currentNode.left != null){
queue.add(currentNode.left);
}
if(currentNode.right != null){
queue.add(currentNode.right);
}
}
return list;
}
// recursive
breathFirstSearchR(queue, list){
if(queue.length == 0){
return list;
}
var currentNode = queue.removeAt(0); //when you remove from queue here the queue becomes empty again at initial stage
list.add(currentNode.value);
if(currentNode.left != null){
queue.add(currentNode.left);
}
if(currentNode.right != null){
queue.add(currentNode.right);
}
return breathFirstSearchR(queue, list);
}
DFSInOrder(root, list){
return traverseInOrder(root,list);
}
DFSPreOrder(root, list){
return traversePreOrder(root,list);
}
DFSPostOrder(root, list){
return traversePostOrder(root,list);
}
traverseInOrder(node, list){
if(node.left != null){
traverseInOrder(node.left,list);
}
list.add(node.value); // this first adds the left nodes values to the list before the right
if(node.right != null){
traverseInOrder(node.right,list);
}
return list;
}
traversePreOrder(node, list){
list.add(node.value); // this first adds the first nodes values to the list before the left before the right
if(node.left != null){
traversePreOrder(node.left,list);
}
if(node.right != null){
traversePreOrder(node.right,list);
}
return list;
}
traversePostOrder(node, list){
if(node.left != null){
traversePostOrder(node.left,list);
}
if(node.right != null){
traversePostOrder(node.right,list);
}
list.add(node.value);
// this first adds the left nodes values to the list before the right then go back up to right left most
return list;
}
@override
String toString(){
return toMap().toString();
}
}
void main(){
BinarySearchTree tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
print(tree.DFSPostOrder(tree.root, []));
// JSON.stringify(traverse(tree.root));
print(tree);
// 9
// 4 20
//1 6 15 170
// function traverse(node) {
// const tree = { value: node.value };
// tree.left = node.left === null ? null : traverse(node.left);
// tree.right = node.right === null ? null : traverse(node.right);
// return tree;
// }
}
Dart
INFO