Q4 (30 points). Write a program to create a binary tree, with the following node struct: typedefstructtreenode1intdata;structtreenodeleft;structtreenode*right;}node;/treenodestruct//integerfield//pointertotheleftchild//pointertotherightchild/ The values of the leaves of a binary tree, from left to right order, form a leaf value sequence. For example, in the given tree, the leaf value sequence is (6,7,4,9,8). Two binary trees are considered leaf-similar if their leaf value sequence is the same. Return true if and only if the two given trees with head nodes root 1 and root2 are leaf-similar. Specify the traversal you use for input sequence (recall that for a given input sequence, different traversal can lead to different binary tree). Example 1: Input: root1 =[3,5,1,6,2,9,8, null,null ,7,4],root2=[3,5,1,6,7,4,2, null,null,null,null,null,null ,9,8] Output: true Example 2: Input: root1=[1,2,3],root2=[1,3,2] Output: false