Graph Traversal using DFS is an obvious way to traverse a tree with recursion. Below is an algorithm for traversing binary tree using DFS.
Prerequisites
Algorithm
- Initialize the current node as root node and the parent as -1.
- Traverse the Binary Tree as the in the general DFS fashion and keep of increasing the level of the node as we traverse farther from the root node.
- While traversing we check if the level of the current node of the binary tree is even then add in even sum else add in odd sum.
- Finally, print the Absolute difference of the of even sum and the odd sum.
Example
Java
import java.util.*;public class GFG { // global variable declaration static ArrayList<ArrayList<Integer> > arr; static int val[]; static int sum_odd = 0, sum_even = 0; // traverses the binary-tree/tree having parameters u, // par, level which denotes current node, current's // parent node, current level of the tree. static void dfs(int u, int par, int level) { // according to level adding the node if (level % 2 == 0) sum_even += val[u]; else sum_odd += val[u]; // exploring the child of the particular node u (2 // in case of binary tree). for (int v : arr.get(u)) { if (v != par) { // recursively calling the current child // node to become parent of the next dfs // call. dfs(v, u, level + 1); } } } public static void main(String args[]) { Scanner in = new Scanner(System.in); int n = 5; val = new int[] { 0, 2, 10, 5, 3, 2 }; // declaration of the ArrayList size arr = new ArrayList<>(); // initialization of each array element as ArrayList // class for (int i = 0; i <= n; i++) arr.add(new ArrayList<>()); arr.get(1).add(2); arr.get(2).add(1); arr.get(1).add(4); arr.get(4).add(1); arr.get(2).add(5); arr.get(5).add(2); arr.get(3).add(4); arr.get(4).add(3); // 1(2) // / \ // 2(10) 4(3) // / / // 5(2) 3(5) // initial call of recursion dfs(1, -1, 0); System.out.println( "Absolute difference of sum of odd and even nodes of a binary tree " + Math.abs(sum_odd - sum_even)); }} |
Output
Absolute difference of sum of odd and even nodes of a binary tree 4
Time Complexity: O(V + E) where V is the vertices and E is the edges.