144. Binary Tree Preorder Traversal

 Problem Statement


Given the root of a binary tree, return the preorder traversal of its nodes' values.

 

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

 

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?


Solution


/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) 

    {

        ArrayList<Integer> list = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();

        if(root == null)

            return list;

        stack.push(root);

        while(stack.size()>0)

        {

            TreeNode temp = stack.pop();

            list.add(temp.val);

            if(temp.right != null)

                stack.push(temp.right);

            if(temp.left != null)

                stack.push(temp.left);

        }

        return list;

    }

}


Linked List Cycle in leetcode

Description:-

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example - 1 :

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?


Program:- 

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode slowPtr=head;

        ListNode fastPtr=head;

        while(fastPtr!=null && fastPtr.next!=null)

        {

            slowPtr=slowPtr.next;

            fastPtr=fastPtr.next.next;

            if(slowPtr==fastPtr)

                return true;

        }

        return false;  

    }

}



                                 Unions



Definition:

  • A union is a special data type available in C that allows the storage of different data types in the same memory location. 
  • Unlike unions structures can stores different data types in different locations.
  • You can define a union with many members, but only one member can contain a value at any given time. 
  • Unions provide an efficient way of using the same memory location for multiple-purpose.


Declaration:

union [union tag] {

   member definition;

   member definition;

   ...

   member definition;

} [declaring one or more union variables]; 


Giving the union tag is optional it works without tag also.


Example:

union Data {

   int i;

   float f;

   char str[45];

} data;


  • Now, a variable of Data type can store an integer, a floating-point number, or a string of characters. It means a single variable(data), i.e., the same memory location, can be used to store multiple types of data. 
  • You can use any built-in or user-defined data types inside a union based on your requirement.
  • The memory occupied by a union will be large enough to hold the largest member of the union. 
  • For example, in the above example, Data type will occupy 45 bytes of memory space because this is the maximum space that can be occupied by a character string. The following example displays the total memory size occupied by the above union example.

Accessing Union Members

Same as Structures To access any member of a union, we use the member access operator (.), and The member access operator is coded as a period between the union variable name and the union member that we wish to access.

Example:

#include <stdio.h>

#include <string.h>

union Shs{

 int i;

 float f;

};

int main( ) {

 union Shs d;        

 data.i = 10;

data.f = 220.5;

strcpy( d.str, "C Programming");

printf( "d.i : %d\n", data.i);

printf( "d.f : %f\n", data.f);

printf( "d.str : %s\n", data.str);

return 0;

}

Output:

d.i : 1917853763

d.f : 4122360580327794860452759994368.000000

d.str : C Programming

Explaination:

As the data is stored in the same location the integer data and the float data has been corrupted or overwritten by the string data so that when we call integer and float data we get some corrupted value and we can see the String data is displayed correctly as it was stored at the last in the union.

if the code is like this

data.i = 10;

printf( "d.i : %d\n", data.i);

data.f = 220.5;

printf( "d.f : %f\n", data.f);

strcpy( d.str, "C Programming");

printf( "d.str : %s\n", d.str);

then the output will be:

d.i : 10

d.f : 220.500000

d.str : C Programming



Note: More examples will be covered in Problems on the C page

Similarly, you can also learn the structures, arrays, and pointers concept also here

If you have any doubts or you want us to create some more concepts or if you can't solve any problems please give it in the form of your comments.


If you like the content we had given and understood it well then give your valuable rating for this page and comment on your experience in the comment box .













Problem Statement - 1:

1)Write a C-Program to input a 3x4 matrix and print in the form of a matrix

Source Code:















Input & Output:


Problem Statement - 2:
Write a program to print the following pattern
                        1
                1    2    1
1        2        3    2    1

Source Code:




Input & Output:

Problem Statement - 3:
Write a program to calculate the factorial of a function using recursive concept with the help of parameter passing and return value.

Source Code:

Input & Output:


Similarly, you can also learn the structures, arrays, unions and pointers concepts in C programming Language.

If you have any doubts or you want us to create some more concepts or if you can't solve any problems please give them in the form of your comments.


If you like the content we had given and understood it well then give your valuable rating for this page and comment on your experience in the comment box .



  Sundar Pichai  CEO @Google and Alphabet

Biography: 

  • Pichai Sundararajan, also known as Sundar Pichai, Pichai was born in Madras (now Chennai), Tamil Nadu, India. 
  • His mother, Lakshmi, was a stenographer, and his father, Regunatha Pichai, was an electrical engineer at GEC, the British conglomerate. His father also had a manufacturing plant that produced electrical components. 
  • Pichai grew up in a two-room apartment in Ashok Nagar, Chennai, and had a Hindu upbringing.


Education: 

  • Pichai completed schooling in Jawahar Vidyalaya Senior Secondary School, a Central Board of Secondary Education school in Ashok Nagar, Chennai. 
  • He completed the Class XII from Vana Vani school at IIT Madras. 
  • Later he cracked the IIT-JEE examinations and joined IIT Kharagpur where he pursued a course in Metallurgy(1993).
  •  After his B-Tech, he like many others of his generation went off to the United States where he completed a Master's in Science from Stanford(1995).
  • Then earned an M.B.A. (2002) from the Wharton School of the University of Pennsylvania.


Professional Career: 

  • After completing his MBA, Pichai initially joined Applied Materials(a supplier of semiconductor materials) as a Product Manager 
  • Then worked as a management consultant with McKinsey. 
  • Pichai joined Google in 2004, where he led the product management and innovation efforts for a suite of Google's client software products, including Google Chrome and Chrome OS, as well as being largely responsible for Google Drive. 
  • Later he worked in google as vice-president of product management and worked on the Toolbar which was designed to simplify search on Microsoft's Internet Explorer and Mozilla's Firefox Toolbar’s success inspired Pichai to launch Google's own browser. 
  • In 2008, Google launched Chrome which became a hit with millions across the world in no time 
  • His stellar performance soon saw Pichai being promoted as the senior vice-president of Google Chrome and Google Apps in 2012 
  • In 2013, Google promoted him as the head of the company's mobile operating system, Android, 
  • By 2014 he was given charge of Search, Maps, and Gmail. With this, the IIT-Kharagpur alumnus became one of the most powerful technology executives in the world. 
  • In 2014, he was one of the candidates in contention for the post of Microsoft CEO, but Google managed to retain him. 
  • In a blog post in August 2015, Larry Page announced the launch of Alphabet and Google became a subsidiary of this new company and Pichai was made the CEO of Google. 
  • In 11 years he rose the ladder and became the operations chief of the technology behemoth which now consisted of Search, Advertising, Maps, YouTube, and Android. 
  • Since he took over, Google's market cap more than doubled to $900 billion. 
  • Pichai’s special interest in India has led Google to tie up with the Indian Railways for high-speed internet at railway stations. 
  • In December 2019, Google’s founders Larry Page and Sergey Brin wrote a letter in which they announced that they were stepping down and appointed Sundar Pichai as the CEO of Alphabet in addition to his existing role of Google CEO.

Similarly you can also learn the structures, arrays, unions and pointers concept in C programming Language.

                                   ARRAYS (C Programming)

Definition:

  1. An array is a collection of similar data type items stored at contiguous(Continuous) memory locations.
  2. The array is the simplest data structure where each data element can be accessed by using its index number.
  3. if you want to store the marks of a student in 6 subjects, then traditionally we need to define different variables for the marks in the different subjects. But Instead of that, we can define an array that can store the marks in each subject at the contiguous memory locations.


Declaration:

  1. In C programming Array can be created as 
  2. data_type array_name[array_size]
  3. Here data_type is to declare whether we want to store integers or characters or floating-point numbers etc.
  4. Array_name is some user-defined name given to your array to be created.
  5. Array_size is the size of the array to be created, as the array must be created with a predefined size


Example:

int shsarray[10];

The array with the name shsarray will be created with size 10.


Initialization:

Initialization of the array can be done along with the declaration.

The index is the number by which we can access the elements of an array.

Index starts from 0 to (size of the array)-1

The array can be initialized in two ways 

1)At the time of the creation 

Example:

int shsarray[10]={1,2,3,4,5,56,7,8,8,5};

Or can also do without declaring the size of the array in this case like below example.

Int shsarray[]={1,2,3,4,5,5,6,67};

2)Individually using indices

int shsarray1[3];

shsarray[0]=34;

shsarray[1]=65;

shsarray[2]=66;


    34

    65

      66

      0                     1               2

Can be accessed by using the same indices like shsarray[1]

Will give output as 65.


Advantages of Using Arrays :

  • Can store and access data items with fewer lines of code

  • Can search for an element easily using indices.

  • Can perform sorting operation easily.


Disadvantages :

  • We can’t change the size of the array dynamically while running if we want to increase or decrease the size of the array because array size should be fixed, at the time of declaration.


Sample program-1:

Output:

1

4

6

8

Sample Program-2:

Output:

101

23

10

9

7

Note: To do in ascending order just change as a[j]<a[i]


Sample program 3:

Output:

Printing Largest element of the array…

10



2 Dimensional Array

  1. The two-dimensional array can be defined as an array of arrays. 
  2. The 2D array is organized as matrices which can be represented as the collection of rows and columns. 


Declaration:

Syntax:

data_type array_name[rows][columns];

Here we have to represent a number of rows and a number of columns in the representation.

Example:

Int twodarray[2][3];

Here a two-dimensional array of name twodarray of 2 rows and 3 columns has been created.


Initialization:

Initialization can be done in two ways same as in the 1D array

1)At the time of the creation 

Example:

int twoDarray[2][3]={{1,2,3},{4,5,56}};

If you initialize without declaring the size of the array, like in the 1D Array

this will not work with 2D arrays. We will have to define at least the second dimension of the array

example.

int twoDarray[][3]={{1,2,3},{4,5,56}};

2)Individually using indices

int twoDarray[2][3];

twoDarray[0][0]=56;

twoDarray[0][1]=2;

twoDarray[0][2]=5;

twoDarray[1][0]=1;

twoDarray[1][1]=15;

twoDarray[1][2]=4;


        00                01              02

      56

      2                  

    5

      1

    15

    4

      10                 11               12       

Can be accessed by using the indices like twoDarray[1][0];

Will give output as 1.


Sample Program 1:

Input:

A[0][0]: 12

A[0][1]: 23

A[1][0]: 34

A[1][1]: 45

Output:

12    23

34    45




Note: More examples will be covered in Problems on C page

Arrays using structures and Arrays using pointers will be covered in the structures and pointers concept respectively

Similarly you can also learn the structures, unions and pointers concept in C programming Language.

If you have any doubts or you want us to create some more concepts or if you can't solve any problems please give it in the form of your comments.


If you like the content we had given and understood it well then give your valuable rating for this page and comment your experience in the comment Box .