react-vite-demo
react and vite demo
git clone https://9o.is/git/react-vite-demo.git
try_tree_taversal.ts
(5078B)
1 type EventsNodeId = {
2 id: string
3 }
4
5 type EventsNode = EventsNodeId & ({
6 events: SHEvent[]
7 children: []
8 } | {
9 events: []
10 children: EventsNode[]
11 })
12
13 type SHEvent = {
14 id: string
15 city: string
16 price: number
17 }
18
19 const eventsNode: EventsNode = {
20 id: "node-a",
21 events: [],
22 children: [{
23 id: "node-b",
24 events: [],
25 children: [{
26 id: "node-c",
27 events: [],
28 children: [
29 {
30 id: "node-d",
31 events: [
32 {
33 id: "a",
34 city: "Los Angeles",
35 price: 100,
36 },
37 {
38 id: "b",
39 city: "New York",
40 price: 200,
41 }
42 ],
43 children: [],
44 },
45 {
46 id: "node-e",
47 events: [],
48 children: [
49 {
50 id: "node-f",
51 events: [
52 {
53 id: "c",
54 city: "Los Angeles",
55 price: 300,
56 },
57 {
58 id: "d",
59 city: "New York",
60 price: 400,
61 }
62 ],
63 children: [],
64 },
65 ],
66 }
67 ],
68 },
69 {
70 id: "node-g",
71 events: [],
72 children: [
73 {
74 id: "node-h",
75 events: [
76 {
77 id: "e",
78 city: "Chicago",
79 price: 500,
80 },
81 {
82 id: "f",
83 city: "Houston",
84 price: 600,
85 }
86 ],
87 children: [],
88 },
89 {
90 id: "node-i",
91 events: [],
92 children: [
93 {
94 id: "node-j",
95 events: [
96 {
97 id: "g",
98 city: "Philadelphia",
99 price: 700,
100 },
101 {
102 id: "h",
103 city: "Houston",
104 price: 800,
105 }
106 ],
107 children: [],
108 },
109 {
110 id: "node-k",
111 events: [
112 {
113 id: "i",
114 city: "Phoenix",
115 price: 900,
116 },
117 {
118 id: "j",
119 city: "Houston",
120 price: 999,
121 }
122 ],
123 children: [],
124 }
125 ],
126 }
127 ],
128 }
129 ],
130 }],
131 }
132
133 // DFS recursive
134 const getEventsDFS = ({ events, children }: EventsNode): SHEvent[] => {
135 if (children.length === 0) { return events }
136 return children.flatMap(child => getEventsDFS(child))
137 }
138
139 // BFS with recursion
140 const bfs = (eventsNode: EventsNode[], result: SHEvent[] = []): SHEvent[] => {
141 if (eventsNode.length === 0) { return result }
142 const [node, ...rest] = eventsNode
143 result.push(...node.events)
144 return bfs([...rest, ...node.children], result)
145 }
146
147 const getEventsBFS = (eventsNode: EventsNode): SHEvent[] => {
148 return bfs([eventsNode])
149 }
150
151 // BFS iterative
152 const getEventsBFSIterative = (eventsNode: EventsNode): SHEvent[] => {
153 const stack = [eventsNode]
154 const result: SHEvent[] = []
155 while (stack.length > 0) {
156 const node = stack.shift() as EventsNode
157 result.push(...node.events)
158 stack.push(...node.children)
159 }
160 return result
161 }
162
163 const getEventsDFSIterative = (eventsNode: EventsNode, result: SHEvent[] = []): SHEvent[] => {
164 result.push(...eventsNode.events)
165 eventsNode.children.forEach(child => getEventsDFSIterative(child, result))
166 return result
167 }
168
169 const actualEvents = getEventsDFSIterative(eventsNode)
170 console.log(actualEvents)