### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: TTree depth-first traversal  (Read 3310 times)

#### Anonimista

• New Member
• Posts: 19
##### TTree depth-first traversal
« on: September 21, 2019, 08:00:40 pm »
I am trying to do a depth-first traversal of a TTree (gtree). The tree I am building looks like

Code: Pascal  [Select][+][-]
1. {*
2. *
3. *         1
4. *       /   \
5. *      2     3
6. *     / \   / \
7. *    4   5 6   7
8. *
9. * }

When using tree.DepthFirstTraverse() I get:

Code: Pascal  [Select][+][-]
1. 1 3 7 6 2 5 4

which is right to left, but I need it to be from left to right, ie

Code: Pascal  [Select][+][-]
1. 1 2 4 5 3 6 7

https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search

I kind of see why this happens from the TTrree source:

Code: Pascal  [Select][+][-]
1. procedure TTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType);
2. var
3.   Stack: TStackType;
4.   Node,Child: TTreeNodeType;
5. begin
6.   if Assigned(FRoot) then begin
7.     Stack := TStackType.Create;
8.     Stack.Push(FRoot);
9.     while Stack.Size > 0 do begin
10.       Node := Stack.Top;
11.       Stack.Pop;
12.       Callback(Node.Data);
13.       for Child in Node.Children do Stack.Push(Child);
14.     end;
15.     Stack.Free;
16.   end;
17. end;

It pushes nodes to a stack and then pops them back so the rightmost nodes get processed first. Here is my test code:

Code: Pascal  [Select][+][-]
1. program project1;
2.
3. {\$mode objfpc}{\$H+}
4.
5. uses
6.     gtree, gvector, sysutils;
7.
8.
9. type
10.
11.     TExpression = class(TObject)
12.     public
13.         value: integer;
14.         constructor Create(v: integer);
15.     end;
16.
17.     TExpressionNode = class(specialize TTreeNode<TExpression>)
18.         destructor Destroy; override;
19.     end;
20.
21.     TExpressionTree = specialize TTree<TExpression>;
22.
23.     TIntVector = specialize TVector<integer>;
24.
25.
26.
27. var
28.     tree: TExpressionTree;
29.     n1, n2, n3, n4, n5, n6, n7: TExpressionNode;
30.     e1, e2, e3, e4, e5, e6, e7: TExpression;
31.
32.     v: TIntVector;
33.     i: integer;
34.
35.
36. constructor TExpression.Create(v: integer);
37. begin
38.     self.value := v;
39. end;
40.
41.
42. destructor TExpressionNode.Destroy;
43. begin
44.     self.Data.Free;
45.     inherited;
46. end;
47.
48.
49. procedure WriteCallback(const e: TExpression);
50. begin
51.     write(e.value, ' ');
52. end;
53.
54.
55. begin
56.
57. {*
58. *
59. *         1
60. *       /   \
61. *      2     3
62. *     / \   / \
63. *    4   5 6   7
64. *
65. * }
66.
67.
68.     e1 := TExpression.Create(1);
69.     e2 := TExpression.Create(2);
70.     e3 := TExpression.Create(3);
71.     e4 := TExpression.Create(4);
72.     e5 := TExpression.Create(5);
73.     e6 := TExpression.Create(6);
74.     e7 := TExpression.Create(7);
75.
76.     n1 := TExpressionNode.Create;
77.     n2 := TExpressionNode.Create;
78.     n3 := TExpressionNode.Create;
79.     n4 := TExpressionNode.Create;
80.     n5 := TExpressionNode.Create;
81.     n6 := TExpressionNode.Create;
82.     n7 := TExpressionNode.Create;
83.
84.     tree := TExpressionTree.Create;
85.
86.     n1.Data := e1;
87.     n2.Data := e2;
88.     n3.Data := e3;
89.     n4.Data := e4;
90.     n5.Data := e5;
91.     n6.Data := e6;
92.     n7.Data := e7;
93.
94.     n1.Children.PushBack(n2);
95.     n1.Children.PushBack(n3);
96.
97.     n2.Children.PushBack(n4);
98.     n2.Children.PushBack(n5);
99.
100.     n3.Children.PushBack(n6);
101.     n3.Children.PushBack(n7);
102.
103.     tree.Root := n1;
104.
105.     tree.DepthFirstTraverse(@WriteCallback);
106.     writeln;
107.
109.     writeln;
110.
111.     tree.Free;
112.
113.     v := TIntVector.Create;
114.
115.     for i := 1 to 10 do
116.     begin
117.         v.PushBack(i);
118.     end;
119.
120.     for i in v do
121.     begin
122.         write(i, ' ');
123.     end;
124.
125.     v.Free;
126.
127.     writeln;
128.
129. end.
130.
131.

The background is I am trying to build an AST from a Pyacc generated parser.
« Last Edit: September 21, 2019, 08:03:51 pm by Anonimista »

#### simone

• Sr. Member
• Posts: 343
##### Re: TTree depth-first traversal
« Reply #1 on: September 22, 2019, 12:07:05 am »

Code: Pascal  [Select][+][-]
1. program project1;
2.
3. {\$mode objfpc}{\$H+}
4.
5. uses
6.     gtree, gvector, sysutils;
7.
8.
9. type
10.
11.     TExpression = class(TObject)
12.     public
13.         value: integer;
14.         constructor Create(v: integer);
15.     end;
16.
17.     TExpressionNode = class(specialize TTreeNode<TExpression>)
18.         destructor Destroy; override;
19.     end;
20.
21.     { TExpressionTree }
22.
23.     TExpressionTree = class(specialize TTree<TExpression>) //inherits from TTree<TExpression>
24.       procedure DepthFirstTraverse(Callback: TDepthFirstCallbackType); //hide original procedure
25.     end;
26.
27.     TIntVector = specialize TVector<integer>;
28.
29.
30.
31. var
32.     tree: TExpressionTree;
33.     n1, n2, n3, n4, n5, n6, n7: TExpressionNode;
34.     e1, e2, e3, e4, e5, e6, e7: TExpression;
35.
36.     v: TIntVector;
37.     i: integer;
38.
39. { TExpressionTree }
40.
41. procedure TExpressionTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType); //new depth first traverse
42. var
43.   Stack: TStackType;
44.   Node{,Child}: TTreeNodeType; //Child variable no longer needed
45.   ind : integer;
46. begin
47.   if Assigned(FRoot) then begin
48.     Stack := TStackType.Create;
49.     Stack.Push(FRoot);
50.     while Stack.Size > 0 do begin
51.       Node := Stack.Top;
52.       Stack.Pop;
53.       Callback(Node.Data);
54.       //for Child in Node.Children do Stack.Push(Child); //(right to left order) replaced by following line
55.       for ind:=Node.Children.Size-1 downto 0 do Stack.Push(Node.Children[ind]); //inverts order of iteration over children
56.     end;
57.     Stack.Free;
58.   end;
59. end;
60.
61.
62. constructor TExpression.Create(v: integer);
63. begin
64.     self.value := v;
65. end;
66.
67.
68. destructor TExpressionNode.Destroy;
69. begin
70.     self.Data.Free;
71.     inherited;
72. end;
73.
74.
75. procedure WriteCallback(const e: TExpression);
76. begin
77.     write(e.value, ' ');
78. end;
79.
80.
81. begin
82.
83. {*
84. *
85. *         1
86. *       /   \
87. *      2     3
88. *     / \   / \
89. *    4   5 6   7
90. *
91. * }
92.
93.
94.     e1 := TExpression.Create(1);
95.     e2 := TExpression.Create(2);
96.     e3 := TExpression.Create(3);
97.     e4 := TExpression.Create(4);
98.     e5 := TExpression.Create(5);
99.     e6 := TExpression.Create(6);
100.     e7 := TExpression.Create(7);
101.
102.     n1 := TExpressionNode.Create;
103.     n2 := TExpressionNode.Create;
104.     n3 := TExpressionNode.Create;
105.     n4 := TExpressionNode.Create;
106.     n5 := TExpressionNode.Create;
107.     n6 := TExpressionNode.Create;
108.     n7 := TExpressionNode.Create;
109.
110.     tree := TExpressionTree.Create;
111.
112.     n1.Data := e1;
113.     n2.Data := e2;
114.     n3.Data := e3;
115.     n4.Data := e4;
116.     n5.Data := e5;
117.     n6.Data := e6;
118.     n7.Data := e7;
119.
120.     n1.Children.PushBack(n2);
121.     n1.Children.PushBack(n3);
122.
123.     n2.Children.PushBack(n4);
124.     n2.Children.PushBack(n5);
125.
126.     n3.Children.PushBack(n6);
127.     n3.Children.PushBack(n7);
128.
129.     tree.Root := n1;
130.
131.     tree.DepthFirstTraverse(@WriteCallback);
132.     writeln;
133.
135.     writeln;
136.
137.     tree.Free;
138.
139.     v := TIntVector.Create;
140.
141.     for i := 1 to 10 do
142.     begin
143.         v.PushBack(i);
144.     end;
145.
146.     for i in v do
147.     begin
148.         write(i, ' ');
149.     end;
150.
151.     v.Free;
152.
153.     writeln;
154.
156.
157. end.
« Last Edit: September 22, 2019, 12:26:45 am by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.6

#### jamie

• Hero Member
• Posts: 2947
##### Re: TTree depth-first traversal
« Reply #2 on: September 22, 2019, 02:24:10 am »
Nice guy you are..

I wish I had  you around when I was doing my home work!
Number 1 at blue screen app creations!

#### avk

• Sr. Member
• Posts: 266
##### Re: TTree depth-first traversal
« Reply #3 on: September 22, 2019, 04:23:35 am »
@Anonimista, another option is to write your own recursive DFS that will do what you need, it is very simple.

#### Anonimista

• New Member
• Posts: 19
##### Re: TTree depth-first traversal
« Reply #4 on: September 22, 2019, 07:14:38 am »
Thank you guys. @avk yes I tend to lose time trying to find a ready-made solution even when it's probably easier to make one myself. oh well

#### simone

• Sr. Member
• Posts: 343
##### Re: TTree depth-first traversal
« Reply #5 on: September 22, 2019, 12:40:55 pm »
@Anonimista, another option is to write your own recursive DFS that will do what you need, it is very simple.

I agree. A recursive DFS would be more compact and elegant (I say this because I spent some time with Lisp and Prolog during my youth). I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
« Last Edit: September 22, 2019, 01:23:29 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.6

#### avk

• Sr. Member
• Posts: 266
##### Re: TTree depth-first traversal
« Reply #6 on: September 22, 2019, 02:23:58 pm »
I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Do you have any benchmark confirming the first thesis? I am interested because my own measurements usually show the opposite.
As for the second, it doesn't seem to matter much, since the TTreeNode destructor is already recursive.

#### simone

• Sr. Member
• Posts: 343
##### Re: TTree depth-first traversal
« Reply #7 on: September 22, 2019, 04:17:18 pm »
I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Do you have any benchmark confirming the first thesis? I am interested because my own measurements usually show the opposite.
As for the second, it doesn't seem to matter much, since the TTreeNode destructor is already recursive.

This fact is well known in literature. See, for example:

https://en.wikipedia.org/wiki/Recursion_(computer_science)#Performance_issues
"Performance issues
In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the compiler used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration."

Sedgewick, Wayne, "Alghorithms", 4th ed. p. 415:
"Generally, recursive implementations are a bit easier to verify for correctness; nonrecursive
implementations are a bit more efficient."
Microsoft Windows 10 64 bit - Lazarus 2.0.6

#### avk

• Sr. Member
• Posts: 266
##### Re: TTree depth-first traversal
« Reply #8 on: September 22, 2019, 04:51:32 pm »
We are not talking about the "grand and terrible" Factorial, but specifically about DFS, right?
Well, personally, I have never been able to write iterative DFS, which would be faster than recursive one.

#### howardpc

• Hero Member
• Posts: 3419
##### Re: TTree depth-first traversal
« Reply #9 on: September 22, 2019, 04:59:00 pm »
"Iterative algorithms are typically faster than recursive ones."
Like many generalisations the correctness of the assertion is often belied by actual measurements.
Algorithms can vary so widely and be used on such varied data that generalisations about comparing them are no better than a rough guide.

Like avk the few times I have done actual measurements on equivalent algorithms chewing their way through identical data I have not found particularly significant speed differences between iterative and recursive methods (provided both routines are well optimsed, of course). Which is not to deny that there are cases where one type of algorithm performs consistently better than the other approach.

#### 440bx

• Hero Member
• Posts: 1832
##### Re: TTree depth-first traversal
« Reply #10 on: September 22, 2019, 04:59:21 pm »
Sedgewick, Wayne, "Alghorithms", 4th ed. p. 415:
"Generally, recursive implementations are a bit easier to verify for correctness; nonrecursive implementations are a bit more efficient."
That's one of the books I keep at hand and, unsurprisingly, he is right.  One thing that should be noted is that, recursion can often be the simplest and most intuitive way of implementing an algorithm but, that doesn't mean it is the best (read, reasonably efficient) way.

Sedgewick's book has a chapter on recursion (chapter 5 in my edition) which provides some examples of the above.  Some algorithms are really simple to implement using recursion but have undesirable Big Os when implemented that way.  That is a problem of the algorithm, not of recursion (like a bubble sort is simply a poor algorithm regardless of how it is implemented.)

Just like everything else, some algorithms can be implemented simply, efficiently and elegantly using recursion, others, not so much.

FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

#### simone

• Sr. Member
• Posts: 343
##### Re: TTree depth-first traversal
« Reply #11 on: September 22, 2019, 05:45:45 pm »
I have not revealed an absolute truth, but a typical situation: in general recursive alghorithms are slightly slower than iterative ones, because they require as many 'calls with return' as the number of recursive cycles.  These types of operations are very expensive for the CPU.  I mentioned authoritative sources in support of my thesis. If someone cites to me equally authoritative sources or shows me experimental evidence of the opposite sign, I am happy to change my mind, because I often use recursive algorithms.
« Last Edit: September 22, 2019, 05:48:47 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.6

#### simone

• Sr. Member
• Posts: 343
##### Re: TTree depth-first traversal
« Reply #12 on: September 22, 2019, 06:26:15 pm »
Moreover, every recursive call requires a stack frame allocation. This is a further cause of slowing down performances and could generate stack overflow. Finally, note that the DFS algorithm implemented by Leledumbo in gtree unit is iterative.
Microsoft Windows 10 64 bit - Lazarus 2.0.6

#### avk

• Sr. Member
• Posts: 266
##### Re: TTree depth-first traversal
« Reply #13 on: September 22, 2019, 08:06:11 pm »
The algorithm implemented by Leledumbo is not equivalent to DFS, otherwise this thread would not have arisen.

#### simone

• Sr. Member
• Posts: 343
##### Re: TTree depth-first traversal
« Reply #14 on: September 22, 2019, 08:30:10 pm »
Yes, I agree. In the gtree unit are implemented a Depth First Traversal and a Breadth First Traversal algorithm. However graph search and graph traversal are very similar algorithms. My posts were not a crusade against recursion! I just wanted to highlight some possible side effects.
« Last Edit: September 22, 2019, 08:41:12 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.6