CODEWITHSUNDEEP
algorithmtreetree-traversal
bradgonesurfing
bradgonesurfing

Reputation: 32162

What's this tree traversal called?

Given a tree with A at the root

A 
+-- B 
|   +-- C
|   +-- D
+-- E 
    +-- F
    +-- G

I want the traversal to be

C,B,A,D,F,E,G

Which could be constructed by starting with all the paths from leaves to the root

C,B,A
D,B,A
F,E,A
G,E,A

and then removing all the nodes that have already been encountered

C,B,A
D
F,E
G

Is there a name for this traversal?

Upvotes: 0

Views: 75

Answers (2)

trincot
trincot

Reputation: 350137

I don't think there is a name for it. As you have defined it, it is not limited to binary trees (unlike "in-order"), and can be used for n-ary trees.

As in the other answer I will provide here a recursive implementation, but using a single stack:

  1. Put the given node on the stack
  2. If the node has children, then apply this routine recursively for each of them
  3. If the node has no children, then pop and visit all nodes from the stack.

Below a JavaScript implementation of that algorithm which will run on the following graph:

           a 
        /     \
      r         e
    / | \     / | \
   G  h  N   d  i  t  
      |     / \    |
      p    o   L   s

The intended traversal would list the nodes in this order: "GraphNodeList"

function traverse(adjacency, id, visit, stack=[]) {
    stack.push(id);
    if (adjacency[id]) {
        for (let child of adjacency[id]) traverse(adjacency, child, visit, stack);
    } else {
        while (stack.length) visit(stack.pop());
    }
}

// Example run
let adjacency = { a: 're', r: 'GhN', h: 'p', e: 'dit', d: 'oL', t: 's' };
traverse(adjacency, 'a', console.log); // log each visited node to console.

Upvotes: 1

grodzi
grodzi

Reputation: 5703

I don't know the name but algorithm can be like: 

half-explore:
    inorder style (I mapped the first "read" element to be the left)
    except for the right node: push it to a FIFO

whenever _half-explored_ some node, get the right node to explore from FIFO and half-explore it


  /*
  A 
  +-- B 
  |   +-- C
  |   +-- D
  +-- E 
      +-- F
          +--H
          +--I
      +-- G 
   */
  let m = [];
  m['A'] = ['B','E'];
  m['B'] = ['C','D'];
  m['E'] = ['F','G'];
  m['F'] = ['H','I'];
  function main(id){
      function leftdfs(id, queue=[]){
          if(m[id]){
              leftdfs(m[id][0], queue);
              console.log(id);
              queue.push(m[id][1]);
          }else{
              console.log(id);
          }
      }
      let queue = [id];
      while(queue.length){
          let id = queue.shift();
          leftdfs(id, queue)
      }
  }
  //CBADHFEIG
  main('A');

Upvotes: 1

Related Questions