Skip to content

Commit 2835864

Browse files
nem035nem035
committed
added inorder tree traversal
1 parent 5416f09 commit 2835864

File tree

8 files changed

+81
-5
lines changed

8 files changed

+81
-5
lines changed

‎algorithm/category.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,8 @@
1515
"tree": {
1616
"name": "Tree",
1717
"list": {
18-
"binary_search_tree": "Binary Search Tree"
18+
"binary_search_tree": "Binary Search Tree",
19+
"binary_tree_traversal": "Binary Tree Traversal"
1920
}
2021
},
2122
"number_theory": {

‎algorithm/tree/binary_tree_traversal/desc.json‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
{
2+
"Binary Tree Traversal": "In computer science, tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.",
3+
"Applications": [
4+
"Pre-order traversal while duplicating nodes and edges can make a complete duplicate of a binary tree.",
5+
"Pre-order traversal can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.",
6+
"In-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).",
7+
"Post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree.",
8+
"Post-order traversal can also generate a postfix representation of a binary tree."
9+
],
10+
"Complexity": {
11+
"time": "Best : O(N) Average : O(logN) Worst : O(N)",
12+
"space": "Worst: O(N) (recursive), Best: O(1) (iterative)"
13+
},
14+
"References": [
15+
"<a href='https://en.wikipedia.org/wiki/Tree_traversal'>Wikipedia</a>"
16+
],
17+
"files": {
18+
"inorder": "Traverse Binary Tree Inorder"
19+
}
20+
}

‎algorithm/tree/binary_tree_traversal/inorder/code.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
var index = 0;
2+
3+
function inorder ( root , parent ) {
4+
if (root === -1) {
5+
logger._print( 'No more nodes. Backtracking.' )._wait ();
6+
return;
7+
}
8+
9+
logger._print( 'Reached ' + root);
10+
treeTracer._visit ( root , parent )._wait ();
11+
12+
logger._print ( ' Going left from ' + root )._wait ();
13+
inorder(T[root][0], root);
14+
15+
logger._print( 'Printing ' + root);
16+
treeTracer._leave ( root );
17+
arrayTracer._notify ( index++, root )._wait();
18+
19+
logger._print ( ' Going right from ' + root )._wait ();
20+
inorder(T[root][1], root);
21+
}
22+
23+
inorder ( 5 ); // node with key 5 is the root

‎algorithm/tree/binary_tree_traversal/inorder/data.js‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
2+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3+
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
4+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
5+
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
6+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
7+
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
8+
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
9+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
10+
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
11+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
13+
];
14+
15+
16+
var T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child
17+
[-1,-1],
18+
[ 0, 2],
19+
[-1,-1],
20+
[ 1, 4],
21+
[-1,-1],
22+
[ 3, 8],
23+
[-1, 7],
24+
[-1,-1],
25+
[ 6,10],
26+
[-1,-1],
27+
[ 9,-1]
28+
];
29+
30+
var treeTracer = new DirectedGraphTracer( " Binary Tree Traversal Inorder ")._setTreeData ( G, 5 );
31+
var arrayTracer = new Array1DTracer( " Binary Tree Print Inorder ")._setData ( new Array(T.length).fill( '-' ) );
32+
var logger = new LogTracer ( " Log ");

‎js/tracer_manager/util/refine_by_type.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,4 +21,4 @@ const refineBoolean = (bool) => {
2121
return bool ? 'T' : 'F';
2222
};
2323

24-
module.exports = refineByType;
24+
module.exports = refineByType;

‎public/algorithm_visualizer.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎public/algorithm_visualizer.js.map‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎public/algorithm_visualizer.min.js.map‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)