Home Web Front-end JS Tutorial Detailed explanation of binary tree traversal in JS

Detailed explanation of binary tree traversal in JS

May 16, 2016 pm 03:10 PM

A binary tree is composed of a root node, a left subtree, and a right subtree. The left subtree and the friend subtree are each a binary tree.
This article mainly implements binary tree traversal in JS.

An example of a binary tree

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

var tree = {

 value: 1,

 left: {

  value: 2,

  left: {

   value: 4

  }

 },

 right: {

  value: 3,

  left: {

   value: 5,

   left: {

    value: 7

   },

   right: {

    value: 8

   }

  },

  right: {

   value: 6

  }

 }

}

Copy after login

Breadth-first traversal

Breadth Priority traversal starts from the first level (root node) of the binary tree and traverses level by level from top to bottom; in the same level, nodes are visited one by one in order from left to right.

Implementation:

Use an array to simulate a queue. First put the root node into the queue. When the queue is not empty, execute a loop: take out a node from the queue, and if the left subtree of the node is not empty, put the left subtree of the node into the queue; if the right subtree of the node is If it is not empty, put the right subtree of the node into the queue.
(The description is a bit unclear, just look at the code.)

1

2

3

4

5

6

7

8

9

10

11

12

13

var levelOrderTraversal = function(node) {

 if(!node) { 

  throw new Error('Empty Tree')

 }

 var que = []

 que.push(node)

 while(que.length !== 0) {

  node = que.shift() 

  console.log(node.value) 

  if(node.left) que.push(node.left) 

  if(node.right) que.push(node.right)

 }

}

Copy after login

Recursive traversal

I feel like using these letters There are three good ways to express recursive traversal:
D: visit the root node, L: traverse the left subtree of the root node, R: traverse the right subtree of the root node.
Pre-order traversal: DLR
In-order traversal: LDR
Post-order traversal: LRD

Following the meaning of the letters, it is traversal. In order ^ ^

These three types of traversal are all recursive traversals, or depth-first traversal (Depth-First Search, DFS), because it always
first accesses deeper.

Recursive algorithm for pre-order traversal:

1

2

3

4

5

6

7

var preOrder = function (node) {

 if (node) { 

  console.log(node.value);

  preOrder(node.left);

  preOrder(node.right);

 }

}

Copy after login

Recursive algorithm for in-order traversal:

1

2

3

4

5

6

7

var inOrder = function (node) {

 if (node) {

  inOrder(node.left); 

  console.log(node.value);

  inOrder(node.right);

 }

}

Copy after login

Recursive algorithm for post-order traversal:

1

2

3

4

5

6

7

var postOrder = function (node) {

 if (node) {

  postOrder(node.left);

  postOrder(node.right); 

  console.log(node.value);

 }

}

Copy after login

Non-recursive depth-first traversal

In fact, for I’m not sure who these concepts belong to. Some books only talk about the above three recursive traversals for binary tree traversal. Some are divided into two types: breadth-first traversal and depth-first traversal, and recursive traversal is divided into depth traversal; some are divided into two types: recursive traversal and non-recursive traversal. Non-recursive traversal includes breadth-first traversal and the following traversal. Personally, it doesn’t matter how you divide it, as long as you master the methods and uses:)

What I just used in breadth-first traversal is a queue. Correspondingly, in this non-recursive depth-first traversal, we use a stack . Still use an array to simulate it in JS.
Here we only talk about preorder:
Well, I tried to describe this algorithm, but it was not clear. Just follow the code and you will understand.

1

2

3

4

5

6

7

8

9

10

11

12

13

var preOrderUnRecur = function(node) {

 if(!node) { 

  throw new Error('Empty Tree')

 }

 var stack = []

 stack.push(node)

 while(stack.length !== 0) {

  node = stack.pop() 

  console.log(node.value) 

  if(node.right) stack.push(node.right) 

  if(node.left) stack.push(node.left)

 }

}

Copy after login

After reading this article, I found the non-recursive post-order algorithm, so I will complete the non-recursive traversal method here.

Non-recursive in-order

First push the left node of the number onto the stack, then take it out, and then push the right node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

var inOrderUnRecur = function(node) {

 if(!node) { 

  throw new Error('Empty Tree')

 }

 var stack = []

 while(stack.length !== 0 || node) { 

  if(node) {

   stack.push(node)

   node = node.left

  } else {

   node = stack.pop()  

   console.log(node.value)

   node = node.right

  }

 }

}

Copy after login

Non-recursive post-order (using a stack)

A temporary variable is used here to record the last push/pop node. The idea is to first push the root node and the left tree onto the stack, then take out the left tree, then push into the right tree, take them out, and finally take the following node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

var posOrderUnRecur = function(node) {

 if(!node) { 

  throw new Error('Empty Tree')

 }

 var stack = []

 stack.push(node)

 var tmp = null

 while(stack.length !== 0) {

  tmp = stack[stack.length - 1] 

  if(tmp.left && node !== tmp.left && node !== tmp.right) {

   stack.push(tmp.left)

  } else if(tmp.right && node !== tmp.right) {

   stack.push(tmp.right)

  } else {  

   console.log(stack.pop().value)

   node = tmp

  }

 }

}

Copy after login

Non-recursive post-order (using two stacks)

The idea of ​​​​this algorithm is similar to the one above, s1 is a bit like a Temporary variables.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

var posOrderUnRecur = function(node) {

 if(node) { 

  var s1 = [] 

  var s2 = []

  s1.push(node) 

  while(s1.length !== 0) {

   node = s1.pop()

   s2.push(node)  

   if(node.left) {

    s1.push(node.left)

   }  

   if(node.right) {

    s1.push(node.right)

   }

  

  while(s2.length !== 0) {  

   console.log(s2.pop().value);

  }

 }

}

Copy after login

Morris traversal

This method implements three depth traversals without recursion or stack, and the space complexity is O(1 ) (I am not particularly clear about this concept)
(I will leave these three algorithms aside and study them when I have time)

Morris order:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

var morrisPre = function(head) {

 if(!head) { 

  return

 }

 var cur1 = head,

   cur2 = null

 while(cur1) {

  cur2 = cur1.left 

  if(cur2) {  

   while(cur2.right && cur2.right != cur1) {

    cur2 = cur2.right

   }  

   if(!cur2.right) {

    cur2.right = cur1   

    console.log(cur1.value)

    cur1 = cur1.left   

    continue

   } else {

    cur2.right = null

   }

  } else {  

    console.log(cur1.value)

  }

  cur1 = cur1.right

 }

}

Copy after login

Morris mid-order:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

var morrisIn = function(head) {

 if(!head) { 

  return

 }

 var cur1 = head,

   cur2 = null

 while(cur1) {

  cur2 = cur1.left 

  if(cur2) {  

   while(cur2.right && cur2.right !== cur1) {

    cur2 = cur2.right

   }  

   if(!cur2.right) {

    cur2.right = cur1

    cur1 = cur1.left   

    continue

   } else {

    cur2.right = null

   }

  

  console.log(cur1.value)

  cur1 = cur1.right

 }

}

Copy after login

Morris post-order:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

var morrisPost = function(head) {

 if(!head) { 

  return

 }

 var cur1 = head,

   cur2 = null

 while(cur1) {

  cur2 = cur1.left 

  if(cur2) {  

   while(cur2.right && cur2.right !== cur1) {

    cur2 = cur2.right

   }  

   if(!cur2.right) {

    cur2.right = cur1

    cur1 = cur1.left   

    continue

   } else {

    cur2.right = null

    printEdge(cur1.left)

   }

  }

  cur1 = cur1.right

 }

 printEdge(head)

}

var printEdge = function(head) {

Copy after login

That’s it I hope the entire content of this article will be helpful to everyone’s learning. For more related tutorials, please visit JavaScript Video Tutorial!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial
1657
14
PHP Tutorial
1257
29
C# Tutorial
1229
24
Demystifying JavaScript: What It Does and Why It Matters Demystifying JavaScript: What It Does and Why It Matters Apr 09, 2025 am 12:07 AM

JavaScript is the cornerstone of modern web development, and its main functions include event-driven programming, dynamic content generation and asynchronous programming. 1) Event-driven programming allows web pages to change dynamically according to user operations. 2) Dynamic content generation allows page content to be adjusted according to conditions. 3) Asynchronous programming ensures that the user interface is not blocked. JavaScript is widely used in web interaction, single-page application and server-side development, greatly improving the flexibility of user experience and cross-platform development.

The Evolution of JavaScript: Current Trends and Future Prospects The Evolution of JavaScript: Current Trends and Future Prospects Apr 10, 2025 am 09:33 AM

The latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.

JavaScript Engines: Comparing Implementations JavaScript Engines: Comparing Implementations Apr 13, 2025 am 12:05 AM

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

JavaScript: Exploring the Versatility of a Web Language JavaScript: Exploring the Versatility of a Web Language Apr 11, 2025 am 12:01 AM

JavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.

Python vs. JavaScript: The Learning Curve and Ease of Use Python vs. JavaScript: The Learning Curve and Ease of Use Apr 16, 2025 am 12:12 AM

Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.

How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration) How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration) Apr 11, 2025 am 08:22 AM

This article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base

From C/C   to JavaScript: How It All Works From C/C to JavaScript: How It All Works Apr 14, 2025 am 12:05 AM

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.

How do I install JavaScript? How do I install JavaScript? Apr 05, 2025 am 12:16 AM

JavaScript does not require installation because it is already built into modern browsers. You just need a text editor and a browser to get started. 1) In the browser environment, run it by embedding the HTML file through tags. 2) In the Node.js environment, after downloading and installing Node.js, run the JavaScript file through the command line.

See all articles